正題

題目鏈接:https://www.luogu.org/problemnew/show/P1344

---

題目大意

要求1不能到n點(diǎn)需要去掉的邊的權(quán)值之和最小，在這樣的情況下求最少去掉的邊。

---

解題思路

對(duì)于每條邊的邊權(quán)分為兩部分一個(gè)是權(quán)值，一個(gè)是割掉的數(shù)量，然后前者比后者優(yōu)先。

那么對(duì)于每個(gè)權(quán)值$w$，就定義為$w?E+1(E>n)$

這樣就分為了$w/E$和$w\%E$兩部分

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ll long long using namespace std; const ll N=320,M=10010,inf=1e18,cs=2333; struct node{ll to,next,w; }a[M*2]; ll tot=1,n,s,t,m,ans; ll dep[N],ls[N]; queue<int> q; void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs() {memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(!dep[y]&&a[i].w){dep[y]=dep[x]+1;if(y==t) return true;q.push(y);}}}return false; } ll dinic(ll x,ll flow) {ll rest=0,k;if(x==t) return flow;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow) return flow;}}if(!rest) dep[x]=0;return rest; } void netflow() {while(bfs())ans+=dinic(s,inf); } int main() {scanf("%lld%lld",&n,&m);s=1;t=n;for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);w=w*cs+1;addl(x,y,w);}netflow(); printf("%lld %lld",ans/cs,ans%cs); }

總結(jié)

以上是生活随笔為你收集整理的P1344-[USACO4.4]追查坏牛奶Pollutant Control【网络流,最小割】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。