求最小割及最小花费
把边权c = c*10000+1
然后跑一个最小割，则flow / 10000就是费用 flow%10000就是边数。
且是边数最少的情况。。
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define ll int #define N 500 #define M 205000 #define inf 107374182 #define inf64 1152921504606846976 struct Edge{ ll from, to, cap, nex; }edge[M*2];//注意这个一定要够大 不然会re 还有反向弧 ll head[N], edgenum; void add(ll u, ll v, ll cap, ll rw = 0){ //如果是有向边则：add(u,v,cap); 如果是无向边则：add(u,v,cap,cap); Edge E = { u, v, cap, head[u]}; edge[ edgenum ] = E; head[u] = edgenum ++; Edge E2= { v, u, rw, head[v]}; edge[ edgenum ] = E2; head[v] = edgenum ++; } ll sign[N]; bool BFS(ll from, ll to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue
q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(ll i = head[u]; i!=-1; i = edge[i].nex) { ll v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false; } ll Stack[N], top, cur[N]; ll Dinic(ll from, ll to){ ll ans = 0; while( BFS(from, to) ) { memcpy(cur, head, sizeof(head)); ll u = from; top = 0; while(1) { if(u == to) { ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的边 for(ll i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(ll i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标 if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top] ].from; } } } return ans; } void init(){memset(head,-1,sizeof head);edgenum = 0;} int n, m, from, to; #define dou 10000 int main(){ int T;scanf("%d",&T); ll i, j, u, v, d; while(T--){ init(); cin>>n>>m>>from>>to; ll all = 0; for(i=1;i<=m;i++){ cin>>u>>v>>d; all += d; d = d*dou+1; add(u,v,d,d); } ll cost = Dinic(from, to); ll bian = cost%dou; cost = all - cost/dou; if(bian==0){puts("Inf");continue;} double ans = (double)cost/(double)bian; printf("%.2lf\n",ans); } return 0; } /* 99 2 0 1 2 4 5 1 4 1 2 1 1 3 1 2 4 2 3 4 2 2 3 1 */