HDU1045 Fire Net
思路：
将每行中每列中被障碍物分割的区域分别进行缩点成为不同的点
将横坐标分成一组，纵坐标分成一组进行二分图最大匹配
#include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int maxn=100; char s[maxn][maxn]; int idx[maxn][maxn],idy[maxn][maxn],matching[maxn],check[maxn]; int n,cntx,cnty; vector<int> a[maxn]; bool dfs(int u) { for (int i=0;i<a[u].size();i++){ int v = a[u][i]; if (!check[v]) { check[v] = true; if (matching[v]==-1||dfs(matching[v])) { matching[v]=u; matching[u]=v; return true; } } } return false; } int hungarian(int cntx) { int ans=0; memset(matching,-1,sizeof(matching)); for (int u=0;u<=cntx;++u){ if(matching[u]==-1){ memset(check, 0, sizeof(check)); if(dfs(u)) ++ans; } } return ans; } void init() { memset(idx,0,sizeof(idx)); memset(idy,0,sizeof(idy)); memset(s,0,sizeof(s)); memset(matching,0,sizeof(matching)); for(int i=0;i<maxn;i++) a[i].clear(); cntx=cnty=0; } int main() { while(scanf("%d",&n)&&n){ init(); for(int i=0;i<n;i++) scanf("%s",s[i]); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(s[i][j]==‘.‘) idx[i][j]=cntx; else if(s[i][j]==‘X‘&&s[i][j+1]!=‘X‘) cntx++; } if(s[i][n-1]!=‘X‘&&s[i+1][0]!=‘X‘&&i!=n-1) cntx++; for(int j=0;j<n;j++){ if(s[j][i]==‘.‘) idy[j][i]=cnty; else if(s[j][i]==‘X‘&&s[j+1][i]!=‘X‘) cnty++; } if(s[n-1][i]!=‘X‘&&s[0][i+1]!=‘X‘&&i!=n-1) cnty++; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(s[i][j]!=‘X‘) a[idx[i][j]].push_back(idy[i][j]+cntx+1); cout<<hungarian(cntx)<<endl; } return 0; }
HDU 2444 The Accomodation of Students
思路：
先用染色法判断是否为二分图，并且将点分组
如果为二分图，就进行最大匹配
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=205; vector<int> a[maxn],l; int color[maxn],matching[maxn],check[maxn],vis[maxn]; int n,m,u,v; void init() { memset(matching,-1,sizeof(matching)); memset(color,-1,sizeof(color)); memset(vis,0,sizeof(vis)); for(int i=0;i<maxn;i++) a[i].clear(); l.clear(); } bool judge() { color[1]=0; queue<int> q; q.push(1); vis[1]=1; while(!q.empty()){ int u=q.front(); if(color[u]==0) l.push_back(u); q.pop(); for(int i=0;i<a[u].size();i++){ int v=a[u][i]; if(vis[v]){ if(color[u]==color[v]) return false; else continue; } else{ vis[v]=1; color[v]=color[u]^1; q.push(v); } } } return true; } bool dfs(int u) { for (int i=0;i<a[u].size();++i){ int v=a[u][i]; if (!check[v]){ check[v]=true; if (matching[v]==-1||dfs(matching[v])){ matching[v]=u; matching[u]=v; return true; } } } return false; } int hungarian() { int ans=0; memset(matching,-1,sizeof(matching)); for(int u=1;u<=n;++u) { if(matching[u]==-1) { memset(check,0,sizeof(check)); if (dfs(u)) ++ans; } } return ans; } int main() { while(scanf("%d%d",&n,&m)!=EOF){ init(); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); a[u].push_back(v); a[v].push_back(u); } if(!judge()) cout<<"No"<<endl; else cout<<hungarian()<<endl; } return 0; }
HDU 1083 Courses
思路：
裸题，直接进行匹配就好了
#include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int maxn=405; vector<int> a[maxn]; int matching[maxn],check[maxn]; int n,m,t,cnt,u,v; bool dfs(int u) { for(int i=0;i<a[u].size();i++){ int v=a[u][i]; if(!check[v]){ check[v]=true; if(matching[v]==-1||dfs(matching[v])){ matching[u]=v; matching[v]=u; return true; } } } return false; } int hungarian() { int ans=0; memset(matching,-1,sizeof(matching)); for(int i=1;i<=n;i++){ if(matching[i]==-1){ memset(check,0,sizeof(check)); if(dfs(i)) ans++; } } return ans; } int main() { scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<=n+m;i++) a[i].clear(); for(int i=1;i<=n;i++){ scanf("%d",&cnt); while(cnt--){ scanf("%d",&u); a[i].push_back(u+n); a[u+n].push_back(i); } } if(hungarian()==n) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
HDU 1281 棋盘游戏
思路：
先进行二分图匹配求出最大匹配数
然后将每个可行点从棋盘中移去看看最大匹配数是否会减少
(邻接矩阵跟邻接表的板子略有不同。。被卡了好久)
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=105; int matching[maxn],check[maxn],s[2*maxn][2*maxn]; int n,m,Cas=1,k,u,v,ans1,ans2; void init() { memset(s,0,sizeof(s)); ans1=ans2=0; } bool dfs(int u) { for(int i=1;i<=m;i++){ if(s[u][i]){ if(!check[i]){ check[i]=true; if(matching[i]==-1||dfs(matching[i])){ //matching[u]=i; matching[i]=u; return true; } } } } return false; } int hungarian() { int ans=0; memset(matching,-1,sizeof(matching)); for(int i=1;i<=n;i++){ memset(check,0,sizeof(check)); if(dfs(i)) ans++; } return ans; } int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF){ init(); for(int i=1;i<=k;i++){ scanf("%d%d",&u,&v); s[u][v]=1; } ans2=hungarian(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]){ s[i][j]=0; if(hungarian()<ans2) ans1++; s[i][j]=1; } } } printf("Board %d have %d important blanks for %d chessmen.\n",Cas++,ans1,ans2); } return 0; }
原文：https://www.cnblogs.com/overrate-wsj/p/12598164.html
