題目大意：
有一張有向圖，對于每個(gè)點(diǎn)，有兩種操作：
1. 刪掉它的所有入邊
2. 刪掉它的所有出邊
對每個(gè)點(diǎn)的每個(gè)操作均有不同的價(jià)值。
求使得圖上沒有邊的最小價(jià)值。
解題思路：
考慮把點(diǎn)拆成入點(diǎn)和出點(diǎn)，然后就是二分圖最小點(diǎn)權(quán)覆蓋集。
也可以考慮最小割。
從S到每個(gè)點(diǎn)的入點(diǎn)連容量為該點(diǎn)執(zhí)行操作2的價(jià)值，每個(gè)點(diǎn)的出點(diǎn)到T連容量為該點(diǎn)執(zhí)行操作1的價(jià)值。對于圖上的每條邊連容量inf的邊。
然后答案就是最小割（割一條S出發(fā)的邊，相當(dāng)于執(zhí)行了2操作，網(wǎng)絡(luò)流不可能從該點(diǎn)再流向其他節(jié)點(diǎn)，則相當(dāng)于刪掉出邊。操作1同理）。

C++ Code：

#include<bits/stdc++.h> using namespace std; const int S=0,T=10005,inf=0x3fffffff; struct edge{int to,nxt,cap; }e[200005]; int head[10050],cnt=1,n,m,level[10050],iter[10050]; inline void addedge(int from,int to,int flow){e[++cnt]=(edge){to,head[from],flow};head[from]=cnt;e[++cnt]=(edge){from,head[to],0};head[to]=cnt; } queue<int>q; void bfs(){level[S]=1;for(q.push(S);!q.empty();){int u=q.front();q.pop();for(int i=head[u];~i;i=e[i].nxt)if(e[i].cap&&!~level[e[i].to]){level[e[i].to]=level[u]+1;q.push(e[i].to);}} } inline int min(int a,int b){return a<b?a:b;} int dfs(int u,int f){if(!f||u==T)return f;for(int& i=iter[u];~i;i=e[i].nxt)if(e[i].cap&&level[e[i].to]>level[u]){int d=dfs(e[i].to,min(f,e[i].cap));if(d){e[i].cap-=d;e[i^1].cap+=d;return d;}else level[e[i].to]=-1;}return 0; } int dinic(){for(int flow=0,f;;){memset(level,-1,sizeof iter);if(bfs(),!~level[T])return flow;memcpy(iter,head,sizeof iter);while(f=dfs(S,inf))flow+=f;} } int main(){memset(head,-1,sizeof head);ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;++i){int p;cin>>p;addedge(i+n,T,p);}for(int i=1;i<=n;++i){int p;cin>>p;addedge(S,i,p);}while(m--){int x,y;cin>>x>>y;addedge(x,y+n,inf);}cout<<dinic()<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Mrsrz/p/9304310.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ1322]Destroying The Graph的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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