板子(匈牙利算法, 邻接矩阵)
- const int MAXN=2e3+5;
- int uN, vN;
- int g[MAXN][MAXN];
- int linker[MAXN];
- bool used[MAXN];
- bool dfs(int u)
- {
- for(int v=0; v<vN; v++)
- if(g[u][v] && !used[v])
- {
- used[v]=true;
- if(linker[v]==-1 || dfs(linker[v]))
- {
- linker[v]=u;
- return true;
- }
- }
- return false;
- }
- int hungary()
- {
- int res=0;
- memset(linker, -1, sizeof(linker));
- for(int u=0; u<uN; u++)
- {
- memset(used, 0, sizeof(used));
- if(dfs(u)) res++;
- }
- return res;
- }
- View Code
- HDU 1045
题意: 给出一张图, 给出空地'.'和隔板'x', 求放置最多满足条件的 blockhouse, 条件: 垂直和水平方向上没有如果隔板隔开的话, 只能放置一个 house, 有隔板话, 隔板的之后 (相对位置) 的不用考虑.
题解: 分别对每一行和每一列进行缩点 (重新标号), 两个相交的话就连边(其实就是把 2 个条件链接(行, 列) 到了一起)
- #include <bits/stdc++.h>
- using namespace std;
- #define _for(i,a,b) for(int i=(a); i<(b); i++)
- #define _rep(i,a,b) for(int i=(a); i<=(b); i++)
- const int MAXN=2e2+5;
- int uN, vN;
- int g[MAXN][MAXN];
- int linker[MAXN];
- bool used[MAXN];
- bool dfs(int u)
- {
- for(int v=0; v<vN; v++)
- if(g[u][v] && !used[v])
- {
- used[v]=true;
- if(linker[v]==-1 || dfs(linker[v]))
- {
- linker[v]=u;
- return true;
- }
- }
- return false;
- }
- int hungary()
- {
- int res=0;
- memset(linker, -1, sizeof(linker));
- for(int u=0; u<uN; u++)
- {
- memset(used, 0, sizeof(used));
- if(dfs(u)) res++;
- }
- return res;
- }
- char Map[MAXN][MAXN];
- int Mrow[MAXN][MAXN], Mcol[MAXN][MAXN];
- int main()
- {
- iOS::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("in.txt", "r", stdin);
- int n;
- while(cin>>n, n)
- {
- _for(i, 0, n) _for(j, 0, n) cin>>Map[i][j];
- uN=vN=0;
- int cu=0, cv=0;
- memset(Mrow, -1, sizeof(Mrow));
- memset(Mcol, -1, sizeof(Mcol));
- _for(i, 0, n) _for(j, 0, n)
- {
- if(Mrow[i][j]==-1 && Map[i][j]=='.')
- {
- for(int k=j; k<n&&Map[i][k]=='.'; k++)
- Mrow[i][k]=cu;
- uN=max(uN, ++cu);
- }
- if(Mcol[i][j]==-1 && Map[i][j]=='.')
- {
- for(int k=i; k<n&&Map[k][j]=='.'; k++)
- Mcol[k][j]=cv;
- vN=max(vN, ++cv);
- }
- }
- memset(g, 0, sizeof(g));
- _for(i, 0, n) _for(j, 0, n)
- if(Map[i][j]=='.') g[Mrow[i][j]][Mcol[i][j]]=1;
- cout<<hungary()<<endl;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3150212.html