最大流最小割

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #define mt(a,b) memset(a,b,sizeof(a))
  7 using namespace std;
  8 const int inf=0x3f3f3f3f;
  9 class Dinic { ///最大流(MV^2*ME)
 10     typedef int typef;///流量的类型
 11     static const int ME=4010;///边的个数
 12     static const int MV=64;///点的个数
 13     int temp[MV],cur[MV],level[MV],path[MV];
 14     bool used[MV];
 15     queue<int> q;
 16     typef flow;
 17     bool bfs(int s,int t) {
 18         mt(level,-1);
 19         while(!q.empty()) q.pop();
 20         q.push(s);
 21         level[s]=1;
 22         while(!q.empty()) {
 23             int u=q.front();
 24             q.pop();
 25             for(int i=g.head[u]; ~i; i=g.e[i].next) {
 26                 int v=g.e[i].v;
 27                 if(level[v]==-1&&g.e[i].flow) {
 28                     level[v]=level[u]+1;
 29                     q.push(v);
 30                     if(v==t) return true;
 31                 }
 32             }
 33         }
 34         return false;
 35     }
 36     struct G {
 37         struct E {
 38             int u,v,next;
 39             typef flow;
 40         } e[ME];
 41         int le,head[MV];
 42         void init() {
 43             le=0;
 44             mt(head,-1);
 45         }
 46         void add(int u,int v,typef flow) {
 47             e[le].u=u;
 48             e[le].v=v;
 49             e[le].flow=flow;
 50             e[le].next=head[u];
 51             head[u]=le++;
 52         }
 53     } g;
 54 public:
 55     typef getflow() {
 56         return flow;
 57     }
 58     void init() {
 59         g.init();
 60     }
 61     void add(int u,int v,typef flow) {
 62         g.add(u,v,flow);
 63         g.add(v,u,0);
 64     }
 65     void solve(int s,int t) {
 66         int p,tempp;
 67         typef now;
 68         bool flag;
 69         flow=0;
 70         while(bfs(s,t)) {
 71             for(int i=0; i<MV; i++) {
 72                 temp[i]=g.head[i];
 73                 used[i]=true;
 74             }
 75             p=1;
 76             path[p]=s;
 77             while(p) {
 78                 int u=path[p];
 79                 if(u==t) {
 80                     now=inf;
 81                     for(int i=1; i<p; i++) {
 82                         now=min(now,g.e[cur[path[i]]].flow);
 83                     }
 84                     flow+=now;
 85                     for(int i=1; i<p; i++) {
 86                         int j=cur[path[i]];
 87                         g.e[j].flow-=now;
 88                         g.e[j^1].flow+=now;
 89                         if(!g.e[j].flow) tempp=i;
 90                     }
 91                     p=tempp;
 92                 } else {
 93                     flag=false;
 94                     for(int i=temp[u]; ~i; i=g.e[i].next) {
 95                         int v=g.e[i].v;
 96                         if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) {
 97                             cur[u]=i;
 98                             temp[u]=g.e[i].next;
 99                             flag=true;
100                             path[++p]=v;
101                             break;
102                         }
103                     }
104                     if(flag) continue;
105                     p--;
106                     used[u]=false;
107                 }
108             }
109         }
110     }
111 } dinic;
112 int main() {
113     int t,n,m,p,q,x,y,z;
114     while(~scanf("%d",&t)) {
115         while(t--) {
116             scanf("%d%d%d%d",&n,&m,&p,&q);
117             dinic.init();
118             int sum=0;
119             for(int i=0; i<m; i++) {
120                 scanf("%d%d%d",&x,&y,&z);
121                 dinic.add(x,y,z*2000+1);
122                 dinic.add(y,x,z*2000+1);
123                 sum+=z;
124             }
125             dinic.solve(p,q);
126             int ans=dinic.getflow();
127             int ans1 = ans/2000;//我是把边的权值乘以2000， 然后+1
128             int ans2 = ans%2000;//这样%2000就是最小割的边数， /2000就是最小割了。
129             if(ans == 0)printf("Inf
");
130             else printf("%.2f
",(sum-ans1)*1.0/ans2);
131         }
132     }
133     return 0;
134 }