最大流 OR 二分圖匹配

題意：輸入n，有n個插座，下面n行是每個插座的類型（最后24個字母來表示一個插座，沒有空格放心用scanf，但是有可能插座會相同，但是這個沒有什么影響）

? ? ? ? ?輸入m，有m個電器，下面m行每行兩個單詞分別是電器的名字和插頭類型（同樣24個字母單詞內沒空格，兩個單詞空格隔開）

? ? ? ? ?輸入k，有k個轉換器，下面k行每行兩個單詞，分別表示轉換器的入口類型和插頭類型

每種轉換器的個數是無限的，轉換器本身可以與轉換器相連

要你求，讓最多的電器能夠插在插座上（可以用轉換器輔助也可以直接插上去），輸入不能插上去的電器的數量

?

思路一：轉化為最大流，重點還是如何建圖，我是用鄰接表建圖的這樣效率也高一點，其實用鄰接矩陣建圖也可以。我的建圖方法是，電器從1到m標號，轉換器從m+1到m+k標號，插座從m+k+1到m+k+n標號，另外設置一個源點s=0，匯點t=m+k+n+1 ， 求s到t的最大流

s與所有電器建一條有向邊，容量為1，所有插座與匯點建一條有向邊，容量為1。對于每個電器，如果能直接和插座相連的，和每個能相連的插座建一條有向邊，容量為1.另外，所有電器和所有能連接上的轉換器建一條有向邊，容量為INF，轉換器和轉換器之間能相連的建一條有向邊容量為INF，轉換器和插座能相連建一條有向邊容量為INF。

建圖完畢，直接EK最大流模板上去即可

注意幾點：

1.鄰接表建有向邊不要忘記每條有向邊附帶一條反邊，反邊的容量為0

2.一定要記得建立電器和插座直接相連的邊

3.一開始想復雜了，認為用電器和插座要拆點，轉換器不用拆點，其實全部都不用拆點

4.不需要建無向圖，另外建無向圖應該是錯的

#include <cstdio> #include <cstring> #include <queue> using namespace std; #define INF 0x3f3f3f3f #define MAXN 550 #define MAXM 50010 int N,M,K,CNT,edgenum,s,t,first[MAXN]; struct edge {int u,v,f,cap,next; }e[MAXM]; struct device //電器 {char s1[30],s2[30]; }d[MAXN]; struct adapter //轉換器 {char s1[30], s2[30]; }a[MAXN]; struct receptacle //插座 {char s[30]; }r[MAXN]; void printfff() //測試打印函數 {printf("M=%d N=%d K=%d CNT=%d s=%d t=%d\n",M,N,K,CNT,s,t);for(int i=0; i<edgenum; i++)printf("%d: %d-->%d=%d %d\n",i,e[i].u,e[i].v,e[i].cap,e[i].next); } void add(int u ,int v , int cap) {int t;e[edgenum].u=u; e[edgenum].v=v;e[edgenum].f=0; e[edgenum].cap=cap;e[edgenum].next=first[u];first[u]=edgenum++;t=u; u=v; v=t;e[edgenum].u=u; e[edgenum].v=v;e[edgenum].f=0; e[edgenum].cap=0;e[edgenum].next=first[u];first[u]=edgenum++; } void input() {scanf("%d",&N);for(int i=1; i<=N; i++)scanf("%s",r[i].s);scanf("%d",&M);for(int i=1; i<=M; i++)scanf("%s%s",d[i].s1,d[i].s2);scanf("%d",&K);for(int i=1; i<=K; i++)scanf("%s%s",a[i].s1,a[i].s2); CNT=N+M+K; } void init() {memset(first,-1,sizeof(first));edgenum=0;s=0; t=CNT+1; //源點,匯點for(int i=1; i<=M; i++) //所有電器{add(s,i,1); //源點和電器建邊容量為1for(int j=1; j<=K ; j++) //所有電器和轉換器的連接if(!strcmp(d[i].s2 , a[j].s1)) //電器可以插入轉換器中add(i,j+M,INF);for(int j=1; j<=N; j++) //電器和插座直接相連if(!strcmp(d[i].s2 , r[j].s))add(i,M+K+j,1);}for(int i=1; i<=K; i++) {for(int j=1; j<=K; j++) //所有轉換器和轉換器之間的連接if(i!=j && !strcmp(a[i].s2 , a[j].s1)) //不用考慮相同種類的轉換器的連接，因為沒有意義add(i+M,j+M,INF);for(int j=1; j<=N; j++) //所有轉換器和所有插座連接if(!strcmp(a[i].s2 , r[j].s)) //轉換器可插入插座中add(i+M , M+K+j , INF); //轉化器和插座相連}for(int i=1; i<=N; i++) //插座和匯點相連add(M+K+i,t,1); } void EK() {queue<int>q;int a[MAXN],path[MAXN];int F;F=0;while(1){memset(path,-1,sizeof(path));memset(a,0,sizeof(a));a[s]=INF;q.push(s);while(!q.empty()){int u=q.front(); q.pop();for(int k=first[u]; k!=-1; k=e[k].next){int v=e[k].v;if(!a[v] && e[k].f<e[k].cap){a[v]=a[u]<e[k].cap-e[k].f?a[u]:e[k].cap-e[k].f;path[v]=k;q.push(v);}}}if(!a[t]) break;for(int k=path[t]; k!=-1; k=path[e[k].u]) //增廣{//printf("%d<--%d ",e[k].v,e[k].u);e[k].f+=a[t];e[k^1].f-=a[t];}//printf("\n");F+=a[t];}//printf("F=%d\n",F);printf("%d\n",M-F); } int main() {int T;scanf("%d",&T);while(T--){input();init();//printfff();EK();if(T) printf("\n");}return 0; }

?

?

?

思路二：二分圖最大匹配

其實用二分圖的思想來看這個問題更加直觀，即電器和插座匹配，（電器之間，插座之間不可能匹配）。問題同樣是建圖問題

用最大流建圖的話，頂點會有轉換器，但是二分圖來建則沒有（當然也不需要加額外的源點和匯點）。二分圖建立的分兩部分，一部分是，用電器能不能直接和某些插座直接相連，能的話直接建邊。另外要利用轉換器，看看能不能把不能直接相連電器和插座給連接起來，能的話就連接。我還沒寫，但是想到是用dfs去找，不知道效率如何。

最后建了二分圖，不需要管那些邊是怎么連接的（直接相連或者借助了轉換器），直接把匈牙利丟上去即可

明天起來再寫二分圖了

?

?

二分圖寫好了，思路就是上面說的那樣，嗯寫二分圖舒心多了，建邊少代碼也少一些。不過我是用dfs去判斷電器能不能通過轉換器連到插座上的，所以時間慢了點，0.060s，上面的最大流是0.008s

另外一個地方是。電器不能直接與插座相連，然后用dfs去找能不能通過轉換器去相連，雖然每種轉換器的數量是無限的，但是在一趟尋找中一種轉換器沒必要被用兩次（其實那種入口和插頭相同的轉換器也沒必要用上，但是不做特殊判斷了，沒影響），也就是可以看成路徑，雖然有環，但是這個環顯然是沒必要經過，所以加了一個vis數組標記

#include <cstdio> #include <cstring> #include <queue> using namespace std; #define INF 0x3f3f3f3f #define MAXN 250 #define MAXM 40100 int N,M,K,CNT,edgenum,first[MAXN],mat[MAXN],vis[MAXN],cov[MAXN]; struct edge {int u,v,next; }e[MAXM]; struct device //電器 {char s1[30],s2[30]; }d[MAXN]; struct adapter //轉換器 {char s1[30], s2[30]; }a[MAXN]; struct receptacle //插座 {char s[30]; }r[MAXN]; void add(int u , int v) {e[edgenum].u=u; e[edgenum].v=v;e[edgenum].next=first[u];first[u]=edgenum++; } int dfs(int j , int k) //目標是j插座,當前是k轉換器 {if(!strcmp(a[k].s2 , r[j].s)) //當前轉換器能插入插座中return 1;vis[k]=1; //標記k轉換器被用過，在一趟dfs中一種轉換器沒必要被用兩次for(int i=1; i<=K; i++) if(!vis[i]) //所有沒被用過的轉換器if(!strcmp(a[k].s2 , a[i].s1)) {//另外k轉換器可以插入i轉換器中if(dfs(j,i))return 1;vis[i]=0;}return 0;} int find(int i , int j) //i電器和j插座 {memset(vis,0,sizeof(vis));for(int k=1; k<=K; k++) //所有轉換器if(!strcmp(d[i].s2 , a[k].s1)) {//電器能插入轉換器的入口if(dfs(j,k))return 1;vis[k]=0;}return 0; } void input() {scanf("%d",&N);for(int i=1; i<=N; i++)scanf("%s",r[i].s);scanf("%d",&M);for(int i=1; i<=M; i++)scanf("%s%s",d[i].s1,d[i].s2);scanf("%d",&K);for(int i=1; i<=K; i++)scanf("%s%s",a[i].s1,a[i].s2); CNT=N+M+K; } void init() {memset(first,-1,sizeof(first));edgenum=0;for(int i=1; i<=M; i++) //所有電器 for(int j=1; j<=N; j++) //所有插座 {if(!strcmp(d[i].s2 , r[j].s)) //可以直接相連 {//printf("直接相連%d---%d\n",i,j);add(i,j+M); //建立有向邊 }else if(find(i,j)) //如果通過轉換器能連接上 {//printf("通過轉換器連接%d---%d\n",i,j);add(i,j+M);}} } void printfff() {for(int i=0; i<edgenum; i++)printf("%d %d %d\n",e[i].u,e[i].v,e[i].next); } int dfs_match(int u) {for(int k=first[u]; k!=-1; k=e[k].next){int v=e[k].v;if(!cov[v]){cov[v]=1;if( mat[v]==-1 || dfs_match(mat[v]) ){ mat[v]=u; return 1; }}}return 0; } void maxmatch() {int max=0;memset(mat,-1,sizeof(mat));for(int i=1; i<=M+N; i++) //所有的點都做一次起點 {memset(cov,0,sizeof(cov));max+=dfs_match(i);}//for(int i=1; i<=M+N; i++)//printf("%d<--->%d\n",i,mat[i]);//printf("max=%d\n",max);printf("%d\n",M-max); } int main() {int T;scanf("%d",&T);while(T--){input();init();//printfff(); maxmatch();if(T) printf("\n");}return 0; }

?

?

總結

以上是生活随笔為你收集整理的uva 753 A Plug for UNIX的全部內容，希望文章能夠幫你解決所遇到的問題。

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