以下題目都是我們學(xué)校內(nèi)部學(xué)生自己出的或改編的題目哦！
LZOI2206 同桌匹配
題目描述：初二（15）由于班主任覺(jué)得一些男生成績(jī)太差，便安排他們班的某位無(wú)聊的班干做一件事。這位班干部需要給這些成績(jī)差的男生分配一些能給予他學(xué)習(xí)動(dòng)力的女同桌。于是，現(xiàn)在有n名同學(xué)（n<=1000）,并且其中的一些女生能給予某些男生學(xué)習(xí)動(dòng)力。現(xiàn)需要給這些男生配同桌，并且要求同桌數(shù)最大，請(qǐng)你輸出最大的同桌數(shù)。 輸入：第1行的2個(gè)數(shù)是n和m（m<=30000）。 接下來(lái)m行中，每行有2個(gè)正整數(shù)x和y，表示學(xué)號(hào)為x的男生與學(xué)號(hào)為y的女生可配為同桌。(數(shù)據(jù)保證任何一個(gè)x都不等于y) 輸出：將求得的最多同桌數(shù)。
解析
是一道二分圖匹配的模板題目。
代碼
#include<bits/stdc++.h>//最基本的模板 using namespace std;int n,m,x,y,g[1001][1001],linker[1001],res;bool used[1001];int dfs(int x){ for(int i=1;i<=n;i++) { if(used[i]==0 && g[x][i]) { used[i]=1; if(linker[i]==0 || dfs(linker[i])) { linker[i]=x; linker[x]=i; return 1; } } } return 0;}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { cin>>x>>y; g[x][y]=1; } for(int i=1;i<=n;i++)linker[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)used[j]=0; if(dfs(i))res++; } cout<<res<<endl;}LZOI2207 宿舍
據(jù)說(shuō)該題改編自洛谷2055 宿舍 題目描述：六中在春晚后總算是放假了 · · · · · · 有些同學(xué)回家了，而有些同學(xué)則有以前的好朋友來(lái)探訪，那么住宿就是一個(gè)問(wèn)題。比如 A 和 B 都是學(xué)校的學(xué)生，A 要回家，而 C 來(lái)看B，C 與 A 不認(rèn)識(shí)。我們假設(shè)每個(gè)人只能睡和自己直接認(rèn)識(shí)的人的床。（我就不信你敢睡你不認(rèn)識(shí)的人的床）那么一個(gè)解決方案就是 B 睡 A 的床而 C 睡 B 的床。而實(shí)際情況可能非常復(fù)雜，有的人可能認(rèn)識(shí)好多在校學(xué)生，在校學(xué)生之間也不一定都互相認(rèn)識(shí)。我們已知一共有 n 個(gè)人，并且知道其中每個(gè)人是不是本校學(xué)生，也知道每個(gè)本校學(xué)生是否回家。問(wèn)是否存在一個(gè)方案使得所有不回家的本校學(xué)生和來(lái)看他們的其他人都有地方住。 輸入：第一行一個(gè)數(shù) T 表示數(shù)據(jù)組數(shù)。接下來(lái) T 組數(shù)據(jù)，每組數(shù)據(jù)第一行一個(gè)數(shù)n 表示涉及到的總?cè)藬?shù)。接下來(lái)一行 n 個(gè)數(shù)，第 i 個(gè)數(shù)表示第 i 個(gè)人是否是在校學(xué)生 (0 表示不是，1 表示是)。再接下來(lái)一行 n 個(gè)數(shù)，第 i 個(gè)數(shù)表示第 i 個(gè)人是否回家 (0 表示不會(huì)家，1 表示回家，注意如果第 i 個(gè)人不是在校學(xué)生，那么這個(gè)位置上的數(shù)是一個(gè)隨機(jī)的數(shù)，你應(yīng)該在讀入以后忽略它)。接下來(lái) n 行每行 n 個(gè)數(shù)，第 i 行第 j 個(gè)數(shù)表示 i 和 j 是否認(rèn)識(shí) (1 表示認(rèn)識(shí)，0 表示不認(rèn)識(shí)，第 i 行 i 個(gè)的值為 0，但是顯然自己還是可以睡自己的床)，認(rèn)識(shí)的關(guān)系是相互的。 輸出：對(duì)于每組數(shù)據(jù)，如果存在一個(gè)方案則輸出 “ ^_^ ”(不含引號(hào)) 否則輸出“T_T”(不含引號(hào))。(注意輸出的都是半角字符，即三個(gè)符號(hào)的 ASCII 碼分別為94,84,95)
解析
這道題其實(shí)是讓我們自己構(gòu)建二分圖，然后再套用模板做就行了（但是還是做了我好久）。
代碼
#include<bits/stdc++.h>using namespace std;int T,n,g[111][111],zx[111],stu[111],bed[111],linker[111],used[111],ans;//zx表示學(xué)生是否在校，stu表示二分圖左邊的學(xué)生，bed表示二分圖右邊的床。 int dfs(int x){ for(int i=1;i<=bed[0];i++) if(!used[bed[i]]&&g[bed[i]][x]) { used[bed[i]]=1; if(!linker[bed[i]]||dfs(linker[bed[i]])) { linker[bed[i]]=x; return 1; } } return 0;}int main(){ cin>>T; while(T--) { memset(zx,0,sizeof(zx));//記得全部初始化 memset(stu,0,sizeof(stu)); memset(bed,0,sizeof(bed)); memset(linker,0,sizeof(linker)); memset(g,0,sizeof(g)); ans=0; cin>>n; for(int i=1;i<=n;i++) cin>>zx[i]; for(int i=1;i<=n;i++) { int x; cin>>x; if(zx[i])//如果是在校學(xué)生 { if(x)bed[++bed[0]]=i; //如果不留校，那么床位增加。 else stu[++stu[0]]=bed[++bed[0]]=i; //如果留校，那么床位和學(xué)生都增加 } else stu[++stu[0]]=i; //如果不是在校學(xué)生，那么學(xué)生增加（構(gòu)建二分圖的過(guò)程） } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>g[i][j]; for(int i=1;i<=n;i++) if(zx[i])g[i][i]=1;//別忘了自己也可以睡自己的床 for(int i=1;i<=stu[0];i++)//又回到了模板題 { memset(used,0,sizeof(used)); if(dfs(stu[i]))ans++; } if(stu[0]>bed[0])ans=-1; //別忘了當(dāng)床數(shù)小于學(xué)生數(shù)時(shí)，絕對(duì)無(wú)法完美匹配哦！ if(ans==stu[0])cout<<"^_^"<<endl; else cout<<"T_T"<<endl; } return 0;}LZOI2208 YZY的信封
據(jù)說(shuō)改編自CODEVS1222 信與信封 題目描述：YZY先生晚上寫(xiě)了n封信(qing shu)，并相應(yīng)地寫(xiě)了n個(gè)信封將信裝好，準(zhǔn)備寄出，給他的班（qing）主（yun）任（tong）。但是，第二天他的兒子Small YZY將這n封信都拿出了信封。不幸的是，Small YZY無(wú)法將拿出的信正確地裝回信封中了。將Small YZY所提供的n封信依次編號(hào)為1，2，…，n；且n個(gè)信封也依次編號(hào)為1，2，…，n。假定Small YZY能提供一組信息：第i封信肯定不是裝在信封j中。請(qǐng)編程幫助Small YZY，盡可能多地將信正確地裝回信封。 輸入：n文件的第一行是一個(gè)整數(shù)n（n≤100）。信和信封依次編號(hào)為1，2，…，n。n接下來(lái)的各行中每行有2個(gè)數(shù)i和j，表示第i封信肯定不是裝在第j個(gè)信封中。文件最后一行是2個(gè)0，表示結(jié)束。 輸出：輸出文件的各行中每行有2個(gè)數(shù)i和j，表示第i封信肯定是裝在第j個(gè)信封中。請(qǐng)按信的編號(hào)i從小到大順序輸出。若不能確定正確裝入信封的任何信件，則輸出“none”。
解析
這道題目還是有一定難度的……思想大概是這樣的：先dfs出一種完美匹配的方法。然后對(duì)于每一個(gè)點(diǎn)，刪去這個(gè)點(diǎn)完美匹配的邊，再次進(jìn)行dfs。若不能完美匹配，則說(shuō)明該點(diǎn)是肯定的。
代碼
#include<bits/stdc++.h>using namespace std;bool g[111][111];int used[111],xlinker[111],ylinker[111],x,y;int n,ans=0;int dfs(int x){ for(int i=1;i<=n;i++) if(used[i]==0 && !g[x][i]) { used[i]=1; if(!ylinker[i]||dfs(ylinker[i])) { ylinker[i]=x; xlinker[x]=i; return 1; } } return 0;} int main(){ cin>>n; while(cin>>x>>y&&x&&y)g[x][y]=1; for(int i=1;i<=n;i++)//先進(jìn)行一次dfs { for(int j=1;j<=n;j++)used[j]=0; if(dfs(i))ans++; } if(ans!=n)cout<<"none"<<endl;//若本來(lái)就不能完美匹配，輸出none else { bool flag=false; for(int i=1;i<=n;i++)used[i]=0; for(int i=1;i<=n;i++)//對(duì)于每個(gè)點(diǎn)，刪去它完美匹配的邊 { int op=xlinker[i]; g[i][op]=1; ylinker[op]=0;xlinker[i]=0; if(!dfs(i)) //若不能完美匹配，則說(shuō)明該點(diǎn)可以肯定，輸出該點(diǎn)和它連接的點(diǎn) { cout<<i<<" "<<op<<endl; xlinker[i]=op; ylinker[op]=i; flag=true; } for(int j=1;j<=n;j++)used[j]=0;//不要忘記初始化 g[i][op]=0; } if(!flag)cout<<"none"<<endl;//若所有點(diǎn)都不能肯定，則輸出none }}關(guān)于二分圖匹配的例題就沒(méi)有了！下期是關(guān)于二分圖判斷哦！~
