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