题面
https://www.luogu.org/problem/P1344
题解
$gyfan$的神仙题。
给每个边一个无限小值的就行了。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #define ri register int #define N 20500 #define INF 1000000007 using namespace std; vector<int> ed[N]; int w[N<<1],to[N<<1]; int n,m,cnt; long long ans; int vis[N],d[N],cur[N]; queue<int> q; void add_edge(int a,int b,int c) { ++cnt; w[cnt]=c; to[cnt]=b; ed[a].push_back(cnt); ++cnt; w[cnt]=0; to[cnt]=a; ed[b].push_back(cnt); } bool bfs(){ vis[1]=1; q.push(1); while (!q.empty()) { int x=q.front(); q.pop(); for (ri i=0;i<ed[x].size();i++) { int e=ed[x][i]; if (vis[to[e]] || !w[e]) continue; vis[to[e]]=1; d[to[e]]=d[x]+1; q.push(to[e]); } } return vis[n]; } int dfs(int x,int lim){ int tl=lim; if (x==n || !lim) return lim; for (ri i=cur[x];i<ed[x].size();i++) { int e=ed[x][i]; if (!w[e] || d[to[e]]!=d[x]+1) continue; int f=dfs(to[e],min(lim,w[e])); if (!f) continue; w[e]-=f; w[1^e]+=f; lim-=f; if (!lim) return tl; cur[x]=i; } return tl-lim; } void dinic(){ while (bfs()) { for (ri i=0;i<=n;i++) vis[i]=0; for (ri i=0;i<=n;i++) cur[i]=0; while (1) { int t=dfs(1,INF); if (!t) break; else ans+=t; } } } int main(){ scanf("%d %d",&n,&m); cnt=-1; for (ri i=1;i<=m;i++) { int a,b,c; scanf("%d %d %d",&a,&b,&c); add_edge(a,b,c*1010+1); } ans=0LL; dinic(); cout<<ans/1010<<" "<<ans%1010<<endl; }