POJ 1273，HDU 1532 Drainage Ditches(最大流)

http://acm.hdu.edu.cn/showproblem.php?pid=1532
使用网络流最大流中的DINIC算法解决
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define point_MAX 10000
 4 #define edge_MAX 100000
 5 #define INF_MAX 999999999
 6 struct EDGE
 7 {
 8     int to;/*指向的点*/
 9     int next;/*指向的下一条邻边*/
10     int w;/*权值*/
11 }edge[edge_MAX];
12 int len;/*边的数量*/
13 int point[point_MAX];
14 int Vertex,Edge;
15 int d[point_MAX];
16 void init()/*初始化*/
17 {
18     len=0;
19     memset(point,0,sizeof(point));
20 }
21 int add_edge(int a,int b,int w)/*添加由a指向b的权值为w的边*/
22 {
23     len++;
24     edge[len].w=w;
25     edge[len].to=b;
26     edge[len].next=point[a];
27     point[a]=len;
28     return 0;/*无重边，插入*/
29 }
30 int bfs(int s)
31 {
32     int q[point_MAX],front=0,rear=1,j,t,i;
33     q[0]=s;
34     memset(d,-1,sizeof(d));/**/
35     d[s]=0;
36     while(front<rear)
37     {
38        t=q[front++];
39          for(j=point[t];j;j=edge[j].next)
40          {
41             if(d[edge[j].to]==-1&&edge[j].w>0)
42             {
43              d[edge[j].to]=d[t]+1;
44            q[rear++]=edge[j].to;
45         }
46          }
47     }
48     if(d[Vertex]>=0)
49        return 1;
50     return 0;
51 }
52 long long min(long long a,long long b)
53 {
54     return a<b?a:b;
55 }
56 long long dinic(int t,long long sum)
57 {
58     int i,os,j;
59     long long a;
60     if(t==Vertex)
61       return sum;
62     os=sum;
63     for(i=point[t];i&&sum;i=edge[i].next)
64     {
65        if(d[edge[i].to]==d[t]+1&&edge[i].w>0)
66        {
67            a=dinic(edge[i].to,min(sum,edge[i].w));
68            edge[i].w-=a;
69            for(j=point[edge[i].to];edge[j].to!=t;j=edge[j].next);
70            edge[j].w+=a;
71            sum-=a;
72        }
73     }
74     return os-sum;
75 }
76 long long DINIC(int s)
77 {
78      long long ans=0;
79      while(bfs(s))
80        ans+=dinic(s,INF_MAX);
81      return ans;
82 }
83 
84 int main()
85 {
86      int i,j,x,y,w;
87      while(scanf("%d%d",&Edge,&Vertex)!=EOF)
88      {
89         init();
90         for(i=0;i<Edge;i++)
91         {
92            scanf("%d%d%d",&x,&y,&w);
93            add_edge(x,y,w);
94            add_edge(y,x,0);
95         }
96         printf("%lld
",DINIC(1));
97      }
98      return 0;
99 }
View Code