二分图匹配
传送门：HUSTOJ
传送门：ACM-ICPC live
象棋盘，‘.’代表兵，‘X’代表车，就是可以攻击同行或同列的任何棋子(要求中间没有兵)。 给你一个n*n的象棋盘，问你最多可以放多少个车，使得他们不相互攻击。
之前看过的题。整理一下思路和教训，补一发题解纪念一下吧。。
既然是每行每列攻击，那么把每行每列拆开。将每行中连续为.的作为X集合中一个点，同样，将每列中连续为.的点作为Y集合中的一个点。对原图中每个’.’，将其对应的X集合和Y集合中的标号建边，便形成了二分图。对该图求最大匹配，每形成一个匹配即选择XY中的行列对应的点放车，那么与它相同编号的行和列都被覆盖了，都不能被选择了。最大匹配数就是最多可以放的车数。附一个带图的教程。%%%
可惜我不会KM算法，网络流解的
WA好几发，因为生成y的点序号时遍历ij搞错了。。。mdzz
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>using namespace std;const int MAXN=200020;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;struct Dinic{ struct Edge{ int from, to, cap, flow;//cap容量 flow流量 Edge(){} Edge(int u, int v, int c, int f){ from=u;to=v;cap=c;flow=f; } }; vector<Edge> edges;//顺序的插入边 vector<int> G[MAXN];//保存边号 bool vis[MAXN];//BFS使用 int d[MAXN]; int cur[MAXN]; void init(int n) { for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0));//单向边第三个参数写0，双向边写cap int t_m=edges.size(); G[from].push_back(t_m-2); G[to].push_back(t_m-1); } bool BFS(int s, int t) { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow)//残量网络 { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a, int s, int t) { if(x==t||a==0) return a; int flow=0, _f; for(int& i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(_f=DFS(e.to, min(a, e.cap-e.flow), s, t))>0) { e.flow+=_f; edges[G[x][i]^1].flow-=_f; flow+=_f; a-=_f; if(a==0) break; } } return flow; } int Maxflow(int s, int t) { int flow=0; while(BFS(s, t)) { memset(cur, 0, sizeof(cur)); flow+=DFS(s, oo, s, t); } return flow; }};Dinic dinic;int main(){ char mp[105][105]; int xmp[105][105]; int ymp[105][105]; int n; while(cin>>n) { dinic.init(200020); memset(mp, 0, sizeof(mp)); memset(xmp, 0, sizeof(xmp)); memset(ymp, 0, sizeof(ymp)); for(int i=0;i<n;i++) { scanf("%s",mp[i]); } int cnt=0, mx=0;; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(mp[i][j]=='.') { if(j!=0&&mp[i][j]==mp[i][j-1]) { xmp[i][j]=cnt; } else { xmp[i][j]=(++cnt); } mx=cnt; } } } int my=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(mp[j][i]=='.') { if(j!=0&&mp[j][i]==mp[j-1][i]) { ymp[j][i]=cnt; } else { ymp[j][i]=(++cnt); } my=cnt; } } } const int sup_s=cnt+1; const int sup_t=cnt+2; for(int i=1;i<=mx;i++) { dinic.AddEdge(sup_s, i, 1); } for(int i=mx+1;i<=my;i++) { dinic.AddEdge(i, sup_t, 1); } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(mp[i][j]=='.') { dinic.AddEdge(xmp[i][j], ymp[i][j], 1); //cout<<xmp[i][j]<<' '<<ymp[i][j]<<endl; } } } int fl=dinic.Maxflow(sup_s, sup_t); cout<<fl<<endl; } //system("pause"); return 0;}新闻热点
疑难解答
