Problem 1228 - 最大匹配 Time Limit: 1000MS Memory Limit: 65536KB Difficulty: Total Submit: 220 Accepted: 31 Special Judge: No Description 有N個人手牽著手（當然可能有的人沒有跟其他任何人牽手），現在需要將他們分組，只有直接牽著手的兩個人才有可能分到一組，問最多能分多少組？ps:因為每個人只有兩只手，最多只能牽兩個人 Input 有多組數據 每組第一行為兩個正整數N,M，表示N個人，M個牽手關系。（1<=N,M<=10000） 接下來M行每行兩個正整數a，b表示a，b兩個牽著手(1<=a,b<=n，a!=b，保證a,b不會重復) Output 對於每組數據，輸出一行，一個正整數即最大能分配的組數 Sample Input 3 3 1 2 2 3 1 3 Sample Output 1 Hint Source cyin 題意： 輸入n m n個點 m個對 輸入m個對 每對表示 a b 可以為一組 （一組只能有2個人，而且1個人不能在2個組中 只有2個人才能組成一個組 。一個人只有2只手 只能牽2個人） 問最多能組成多少個組 思路 ： 二分匹配 [cpp] #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> using namespace std; const int MAXN=11111;//根據點的個數變 int linker[MAXN]; bool used[MAXN]; vector<int>map[MAXN]; int uN; bool dfs(int u) { for(int i=0;i<map[u].size();i++) { if(!used[map[u][i]]) { used[map[u][i]]=true; if(linker[map[u][i]]==-1||dfs(linker[map[u][i]])) { linker[map[u][i]]=u; return true; } } } return false; } int hungary() { int u; int res=0; memset(linker,-1,sizeof(linker)); for(u=0;u<uN;u++) { memset(used,false,sizeof(used)); if(dfs(u)) res++; } return res; } int main() { int u,k,v,i; int n,m; while(scanf("%d %d",&n,&m)!=EOF) { for( i=0;i<MAXN;i++) map[i].clear(); for(i=0;i<m;i++) { scanf("%d %d",&v,&u); v=v-1;//如果點是從1開始計數的 要減1 如果從0開始去掉這句以及下面那句 u=u-1; map[u].push_back(v); map[v].push_back(u); } uN=n; printf("%d\n",hungary()/2); } return 0; } 由於只能牽2個人的手 那麼可以用並查集做 每個人只能只有一個父親節點 且只有一個兒子節點 那麼能牽手的人組成了一條線 那麼這個線上的人 每2個成為一組 線上人數除以2 加上所有線上的結果就是答案 [cpp] #include <stdio.h> #include <string.h> int ss[10022]; int a[10022]; int f(int x) { while(x!=a[x]) x=a[x]; return a[x]; } int main() { int i,j,m,n; int x1,x2; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { a[i]=i; ss[i]=0; } memset(ss,0,sizeof(ss)); while(m--) { scanf("%d%d",&x1,&x2); x1=f(x1); x2=f(x2); if(x1<x2) { a[x2]=x1; } else a[x1]=x2; } int s=0; for(i=1;i<=n;i++) { ss[f(a[i])]++; } for(i=1;i<=n;i++) { s=s+ss[i]/2; } printf("%d\n",s); } return 0; }
