二分圖匹配
傳送門：HUSTOJ
傳送門：ACM-ICPC live
象棋盤，‘.’代表兵，‘X’代表車，就是可以攻擊同行或同列的任何棋子(要求中間沒有兵)。 給你一個n*n的象棋盤，問你最多可以放多少個車，使得他們不相互攻擊。
之前看過的題。整理一下思路和教訓(xùn)，補一發(fā)題解紀(jì)念一下吧。。
既然是每行每列攻擊，那么把每行每列拆開。將每行中連續(xù)為.的作為X集合中一個點，同樣，將每列中連續(xù)為.的點作為Y集合中的一個點。對原圖中每個’.’，將其對應(yīng)的X集合和Y集合中的標(biāo)號建邊，便形成了二分圖。對該圖求最大匹配，每形成一個匹配即選擇XY中的行列對應(yīng)的點放車，那么與它相同編號的行和列都被覆蓋了，都不能被選擇了。最大匹配數(shù)就是最多可以放的車數(shù)。附一個帶圖的教程。%%%
可惜我不會KM算法，網(wǎng)絡(luò)流解的
WA好幾發(fā)，因為生成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));//單向邊第三個參數(shù)寫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)//殘量網(wǎng)絡(luò) { 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;}新聞熱點
疑難解答
