本文共 1702 字，大约阅读时间需要 5 分钟。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a G[240005]; int level[20005],iter[20005]; void add_edge(int u,int v,int cost) { G[u].push_back(edge{ v,cost,G[v].size()}); G[v].push_back(edge{ u,0,G[u].size()-1}); } void bfs(int s) { queue q; q.push(s); level[s]=1; while(q.size()) { int now=q.front();q.pop(); for(int i=0;i 0) { edge e=G[now][i]; if(level[e.to]<0) { level[e.to]=level[now]+1; q.push(e.to); } } } } int dfs(int s,int t,int minn) { if(s==t) return minn; for(int &i=iter[s];i level[s]&&e.cap>0) { int k=dfs(e.to,t,min(minn,e.cap)); if(k>0) { e.cap-=k; G[e.to][e.rev].cap+=k; return k; } } } return 0; } int max_flow(int s,int t) { int ans=0,temp; for(;;) { memset(level,-1,sizeof(level)); bfs(s); if(level[t]<0) return ans; memset(iter,0,sizeof(iter)); while((temp=dfs(s,t,inf))>0) ans+=temp; } } int main() { int n,m,s,t; while(~scanf("%d %d",&n,&m)) { for(int i=1;i<=n;i++) { scanf("%d %d",&s,&t); add_edge(0,i,t); add_edge(i,n+1,s); } for(int j=1;j<=m;j++) { int x,y,c; scanf("%d %d %d",&x,&y,&c); add_edge(x,y,c); add_edge(y,x,c); } printf("%d\n",max_flow(0,n+1)); } return 0; }
转载地址：http://ktgsi.baihongyu.com/