2017寒假集訓 3-D

UVALive - 6525 Attacking rooks

二分圖比對

傳送門：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=;
const int oo=;
typedef long long LL;
const LL loo=l;
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=;i<n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, ));
        edges.push_back(Edge(to, from, , ));//單向邊第三個參數寫0，雙向邊寫cap
        int t_m=edges.size();
        G[from].push_back(t_m-);
        G[to].push_back(t_m-);
    }

    bool BFS(int s, int t)
    {
        memset(vis, , sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s]=;
        vis[s]=;
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int i=;i<G[x].size();i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow)//殘量網絡
                {
                    vis[e.to]=;
                    d[e.to]=d[x]+;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int a, int s, int t)
    {
        if(x==t||a==) return a;
        int flow=, _f;
        for(int& i=cur[x];i<G[x].size();i++)
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+==d[e.to]&&(_f=DFS(e.to, min(a, e.cap-e.flow), s, t))>)
            {
                e.flow+=_f;
                edges[G[x][i]^].flow-=_f;
                flow+=_f;
                a-=_f;
                if(a==) break;
            }
        }
        return flow;
    }
    int Maxflow(int s, int t)
    {
        int flow=;
        while(BFS(s, t))
        {
            memset(cur, , sizeof(cur));
            flow+=DFS(s, oo, s, t);
        }
        return flow;
    }
};
Dinic dinic;
int main()
{
    char mp[][];
    int xmp[][];
    int ymp[][];
    int n;
    while(cin>>n)
    {
        dinic.init();
        memset(mp, , sizeof(mp));
        memset(xmp, , sizeof(xmp));
        memset(ymp, , sizeof(ymp));
        for(int i=;i<n;i++)
        {
            scanf("%s",mp[i]);
        }
        int cnt=, mx=;;
        for(int i=;i<n;i++)
        {
            for(int j=;j<n;j++)
            {
                if(mp[i][j]=='.')
                {
                    if(j!=&&mp[i][j]==mp[i][j-])
                    {
                        xmp[i][j]=cnt;
                    }
                    else
                    {
                        xmp[i][j]=(++cnt);
                    }
                    mx=cnt;
                }
            }
        }

        int my=;
        for(int i=;i<n;i++)
        {
            for(int j=;j<n;j++)
            {
                if(mp[j][i]=='.')
                {
                    if(j!=&&mp[j][i]==mp[j-][i])
                    {
                        ymp[j][i]=cnt;
                    }
                    else
                    {
                        ymp[j][i]=(++cnt);
                    }
                    my=cnt;
                }
            }
        }
        const int sup_s=cnt+;
        const int sup_t=cnt+;
        for(int i=;i<=mx;i++)
        {
            dinic.AddEdge(sup_s, i, );
        }
        for(int i=mx+;i<=my;i++)
        {
            dinic.AddEdge(i, sup_t, );
        }
        for(int i=;i<n;i++)
        {
            for(int j=;j<n;j++)
            {
                if(mp[i][j]=='.')
                {
                    dinic.AddEdge(xmp[i][j], ymp[i][j], );
                    //cout<<xmp[i][j]<<' '<<ymp[i][j]<<endl;
                }
            }
        }
        int fl=dinic.Maxflow(sup_s, sup_t);
        cout<<fl<<endl;
    }
    //system("pause");
    return ;
}