USACO Pollutant Control

本题的意思：在图G中删除某几条边，使1点与N点不联通，并且保证删去边的权值和最小。
可以使用网络流建模：即把删除一条边造成的损失作为该边的容量，根据最大流最小割原理，1->N的最大流就是使1与N不联通的最小割权值。

下面的问题就是要找出符合下列要求的最小割：
1、边数最小；
2、在满足1条件下，若有多个解，输出排序后最小边序号最小的

先介绍几个概念：
1、如果说边E对于网络G是关键的，那么把E从G中移除后，G'的最大流加上E的容量一定等于G的最大流。
2、如果E对网络G是关键的，那么E一定在G的某个最小割上

本人认为该题的正解应该是先找出所有的对G关键的边，然后用DFSID找出边数最小的最小割。可是，本体边数上限是1000，这种方法显然会超时。因此，改用一种不严谨的方法：贪心。也许是因为这题数据没有考虑到贪心，所以很容易就通过了。

此外，这题数据中有重边情况，要注意处理。

代码如下：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define INFINITY 20000000
005
006 typedef struct node
007 {
008     int i,j;
009     int id;
010     long cap;
011 }node;
012
013 int N,M;
014 long cap[35][35];   //容量
015 long residual[35][35];   //剩余网络
016 long flow[35][35];
017 node edge[1020];   //边集数组
018
019 long getmin(long a,long b)
020 {
021     if(a < b)    return a;
022     return b;
023 }
024
025 void init()
026 {
027     int k,i,j;
028     long tmp;
029     scanf("%d%d",&N,&M);
030     for(k = 0;k < M;k ++)
031     {
032         scanf("%d%d",&i,&j);
033         scanf("%ld",&tmp);
034         cap[i][j] += tmp;
035         edge[k].i = i;
036         edge[k].j = j;
037         edge[k].cap = tmp;
038         edge[k].id = k + 1;
039     }
040 }
041
042 int prev[35];
043 long BFS()    //BFS寻找增广路
044 {
045     static int queue[100];
046     static int visit[35];
047     static int f[35];
048     int head,tail;
049     int now,i;
050     memset(f,0,sizeof(f));
051     memset(visit,0,sizeof(visit));
052     head = tail = 0;
053     queue[tail ++] = 1;
054     f[1] = INFINITY;
055     visit[1] = 1;
056     prev[1] = 0;
057     while(head < tail)
058     {
059         now = queue[head ++];
060         if(now == N)    return f[N];
061         for(i = 1;i <= N;i ++)
062             if(residual[now][i] > 0 && !visit[i])
063             {
064                 f[i] = getmin(residual[now][i],f[now]);
065                 queue[tail ++] = i;
066                 visit[i] = 1;
067                 prev[i] = now;
068             }
069     }
070     return 0;
071 }
072
073 long maxflow()
074 {
075     long max = 0;
076     long m;
077     int i;
078     while(1)
079     {
080         m = BFS();
081         if(m == 0)    break;
082         for(i = N;prev[i] > 0;i = prev[i])
083         {
084             residual[prev[i]][i] -= m;
085             residual[i][prev[i]] += m;
086         }
087         max += m;
088     }
089     return max;
090 }
091
092 int cmp(const void *a,const void *b)
093 {
094     node *m,*n;
095     m = (node *)a;
096     n = (node *)b;
097     if(m->cap < n->cap)    return 1;
098     else if(m->cap == n->cap)
099     {
100         if(m->id > n->id)    return 1;
101     }
102     return 0;
103 }
104
105 int main()
106 {
107     freopen("milk6.in","r",stdin);
108     freopen("milk6.out","w",stdout);
109     int i;
110     int cnt;
111     long initmax,max,tmpmax;
112     int cut[1020];   //标记是否删去
113     init();
114     memcpy(residual,cap,sizeof(residual));
115     initmax = maxflow();    //最小割的容量和
116    
117     qsort(edge,M,sizeof(node),cmp);
118     memset(cut,0,sizeof(cut));
119     cnt = 0;
120     for(i = 0;i < M;i ++)
121     {
122         if(edge[i].cap > initmax)    continue;   //直接排除
123         memcpy(residual,cap,sizeof(residual));
124         max = maxflow();
125         cap[edge[i].i][edge[i].j] -= edge[i].cap;
126         memcpy(residual,cap,sizeof(residual));
127         tmpmax = maxflow();
128         if(max - tmpmax == edge[i].cap)   //这条边是关键的
129         {
130             cnt ++;
131             cut[edge[i].id] = 1;
132         }
133         else    cap[edge[i].i][edge[i].j] += edge[i].cap;   //否则复原
134         if(tmpmax == 0)    break;  //从1->N已经没有流量了，结束
135     }
136     printf("%ld %d\n",initmax,cnt);
137     for(i = 1;i <= M;i ++)
138         if(cut[i])    printf("%d\n",i);
139     fclose(stdout);
140     return 0;
141 }