求最小割边的数目
w=w*300+1
ans%300;
#include<iostream> #include<math.h> #include<stdio.h> #include<algorithm> #include<string.h> #include<vector> #include<queue> #include<map> typedef long long ll; using namespace std; #define MAXN 1010 #define inf 1000000000 struct node { int v,w,next; }edge[2010]; int S,T; int head[MAXN],cnt,vis[MAXN]; void add(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].w=0; edge[cnt].next=head[v]; head[v]=cnt++; } queue<int>q1; bool bfs() { memset(vis,-1,sizeof(vis)); vis[S]=0; q1.push(S); while(!q1.empty()) { int now=q1.front(); q1.pop(); for(int i=head[now];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]<0&&edge[i].w>0) { vis[v]=vis[now]+1; q1.push(v); } } } // for(int i=1;i<=4;i++) // cout<<vis[t]<<" "<<endl; return vis[T]!=-1; } int dfs(int u,int w) { if(u==T) return w; int ans=0; for(int i=head[u];i!=-1&&ans<w;i=edge[i].next) { int v=edge[i].v; if(vis[v]==vis[u]+1&&edge[i].w>0) { int b=dfs(v,min(w-ans,edge[i].w)); edge[i].w-=b; edge[i^1].w+=b; ans=ans+b; } } if(!ans) vis[u]=-2; return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); scanf("%d%d",&S,&T); cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w*300+1); } int ans=0; while(bfs()) { // cout<<1<<endl; ans=ans+dfs(S,inf); // } printf("%d ",ans%300); } return 0; }