【BZOJ4405】【WC2016】挑戰NPC（帶花樹）

題面

BZOJ
洛谷
Uoj

Description

小N最近在研究NP完全問題，小O看小N研究得熱火朝天，便給他出了一道這樣的題目：
有n個球，用整數1到n編號。還有m個筐子，用整數1到m編號。
每個筐子最多能裝3個球。
每個球只能放進特定的筐子中。具體有e個條件，第i個條件用兩個整數vi和ui描述，表示編號為vi的球可以放進編號為ui的筐子中。
每個球都必須放進一個筐子中。如果一個筐子內有不超過1個球，那么我們稱這樣的筐子為半空的。
求半空的筐子最多有多少個，以及在最優方案中，每個球分別放在哪個筐子中。
小N看到題目后瞬間沒了思路，站在旁邊看熱鬧的小I嘿嘿一笑：“水題！”
然后三言兩語道出了一個多項式算法。
小N瞬間就驚呆了，三秒鐘后他回過神來一拍桌子：
“不對！這個問題顯然是NP完全問題，你算法肯定有錯！”
小I淺笑：“所以，等我領圖靈獎吧!”
小O只會出題不會做題，所以找到了你——請你對這個問題進行探究，并寫一個程序解決此題。

Input

第一行包含1個正整數T，表示有T組數據。
對于每組數據，第一行包含3個正整數n,m,e，表示球的個數，筐子的個數和條件的個數。
接下來e行,每行包含2個整數vi,ui，表示編號為vi的球可以放進編號為ui的筐子。

Output

對于每組數據，先輸出一行，包含一個整數，表示半空的筐子最多有多少個。

Sample Input

1

4 3 6

1 1

2 1

2 2

3 2

3 3

4 3

Sample Output

2

HINT

對于所有數據，T≤5，1≤n≤3m。保證 1≤vi≤n,1≤ui≤m，且不會出現重復的條件。

保證至少有一種合法方案,使得每個球都放進了筐子,且每個筐子內球的個數不超過 3。

M<=100

題解

考慮一下可以放的球數和對答案的貢獻：
3個球:1
2個球:1
1個球:0
0個球:0
我們發現就是可以放的球數整除\(2\)的結果
所以，把一個籃子拆成三個
一個球還是一個球
如果一個球可以放進一個籃子里，證明著球可以與籃子拆分出來的任意一個點匹配
現在要求的相當于籃子自身能夠匹配的最大數目
如果超過了兩個空，那么就可以自身與自身匹配了，從而產生貢獻一。

所以考慮如下構圖：
每個籃子是三個點，點與點之間互相連邊
每個球是一個點，可以向它可以放的籃子拆出來的三個點連邊。

這樣的話，因為保證所有球都有匹配，
所以最大匹配數=球數+有貢獻的籃子自身的匹配

所以最后的答案就是最大匹配數-球數。

至于如何計算方案，一定優秀增廣球，再增廣籃子，否則會出現籃子自身優先匹配，然后球沒有匹配的情況，到時方案錯誤（雖然答案也是對的。。。）

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define ll long long #define RG register #define MAX 1111 inline int read() {RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t; } struct Line{int v,next;}e[MAX*MAX]; int h[MAX],cnt=1; inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;} queue<int> Q; int dfn[MAX],tim; int match[MAX],pre[MAX]; int f[MAX],vis[MAX],n,m,E; int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);} int lca(int u,int v) {++tim;u=getf(u);v=getf(v);while(dfn[u]!=tim){dfn[u]=tim;u=getf(pre[match[u]]);if(v)swap(u,v);}return u; } void Blossom(int x,int y,int w) {while(getf(x)!=w){pre[x]=y,y=match[x];if(vis[y]==2)vis[y]=1,Q.push(y);if(getf(x)==x)f[x]=w;if(getf(y)==y)f[y]=w;x=pre[y];} } bool Aug(int S) {for(int i=1;i<=n+m+m+m;++i)f[i]=i,vis[i]=pre[i]=0;while(!Q.empty())Q.pop();Q.push(S);vis[S]=1;while(!Q.empty()){int u=Q.front();Q.pop();for(int i=h[u];i;i=e[i].next){int v=e[i].v;if(getf(u)==getf(v)||vis[v]==2)continue;if(!vis[v]){vis[v]=2;pre[v]=u;if(!match[v]){for(int x=v,lst;x;x=lst)lst=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;return true;}vis[match[v]]=1,Q.push(match[v]);}else{int w=lca(u,v);Blossom(u,v,w);Blossom(v,u,w);}}}return false; } void init() {memset(h,0,sizeof(h));cnt=1;memset(dfn,0,sizeof(dfn));tim=0;memset(match,0,sizeof(match)); } int main() {int T=read();while(T--){n=read();m=read();E=read();init();int ans=0;for(int i=1;i<=m;++i){Add(i,i+m);Add(i+m,i);Add(i,i+m+m);Add(i+m+m,i);Add(i+m,i+m+m);Add(i+m+m,i+m);}for(int i=1;i<=E;++i){int v=read(),u=read();Add(v+m+m+m,u);Add(u,v+m+m+m);Add(v+m+m+m,u+m);Add(u+m,v+m+m+m);Add(v+m+m+m,u+m+m);Add(u+m+m,v+m+m+m);}for(int i=m+m+m+n;i;--i)if(!match[i]&&Aug(i))++ans;printf("%d\n",ans-n);for(int i=1;i<=n;++i)printf("%d ",(match[i+m+m+m]-1)%m+1);puts("");}return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/8719429.html

總結

以上是生活随笔為你收集整理的【BZOJ4405】【WC2016】挑战NPC（带花树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。