luogu 1344
首先題意就是裸的最小割啦
然后考慮如何統計邊數
這里有一個trick：
我們設定一個大于$m$的閾值，對于每條邊的邊權我們乘這個閾值+1后跑最小割，得到的答案除以閾值就是真正的最小割，取模閾值后就是最少割掉的邊數
為什么？
我們考慮：設原來的最小割割掉的邊權為$v_{1},v_{2}...v_{n}$，那么乘閾值+1后割掉的邊權就是$v_{1}*lim+1,v_{2}*lim+1...v_{n}*lim+1$
也就是$lim(v_{1}+v_{2}+...+v_{n})+n$
注意到$lim$大于邊權，因此我們直接跑出最小割分解就是答案
而且顯然，加一不會影響最小割的正確性
貼代碼：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ll long long using namespace std; const ll lim=5000; const ll inf=0x3f3f3f3f3f3f3f3fll; struct Edge { int nxt; int to; ll val; }edge[2005]; int head[50]; int dis[50]; int cur[50]; int cnt=1; int n,m; void add(int l,int r,ll w) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; } void dadd(int l,int r,ll w) { add(l,r,w),add(r,l,0); } int ide(int x) { return x&1?x+1:x-1; } bool bfs() { memcpy(cur,head,sizeof(head)); memset(dis,0,sizeof(dis)); dis[1]=1; queue <int> M; M.push(1); while(!M.empty()) { int u=M.front(); M.pop(); for(int i=head[u];i;i=edge[i].nxt) { int to=edge[i].to; if(!dis[to]&&edge[i].val)dis[to]=dis[u]+1,M.push(to); } } return dis[n]; } ll dfs(int x,ll lim) { if(x==n)return lim; ll ret=0; for(int i=cur[x];i;i=edge[i].nxt) { cur[x]=i; int to=edge[i].to; if(edge[i].val&&dis[to]==dis[x]+1) { ll temp=dfs(to,min(lim,edge[i].val)); if(temp) { ret+=temp; lim-=temp; edge[i].val-=temp; edge[ide(i)].val+=temp; if(!lim)return ret; } } } return ret; } ll dinic() { ll ans=0; while(bfs())ans+=dfs(1,inf); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; ll z; scanf("%d%d%lld",&x,&y,&z); z=z*lim+1; dadd(x,y,z); } ll s=dinic(); printf("%lld %lld\n",s/lim,s%lim); return 0; }
浙公網安備 33010602011771號