ARC074F：「Lotus Leaves」

题外话：

先阐述一下我对AtCoder题目的基本印象：

…を出力せよ！！！！

…を出力せよ！！！！

…を出力せよ！！！！…

题目大意：

给定一个的网格图，o是可以踩踏的点，.是不可踩踏的点。

现有一人在S处，向T移动，若此人现在在上，那么下一步他可以移动到或上。

问最少需要将多少个o改成.，可以使这个人无法从S到达T，输出最少需要更改的数目；如果无论如何都不能使这个人无法从S到T，则输出-1

SAMPLE I/O

I #1

3 3
S.o
.o.
o.T

O #1

2

思路：

我们容易想到这道题让我们求的是最小割，根据最小割=最大流定理，考虑建图跑最大流。从S点到同行同列的每一个可踩踏的点连一条边，然后与T同行同列的可踩踏点与T连一条边，然后每一个可踩踏点都与同行同列的可踩踏点连一条边，跑最大流。但是这种方案连出来的边数是级的，跑最大流肯定会超时，考虑优化。

注意到每个点代表了从这个点可以到达第行或者可以到达第列，也就是相当于这个点就是相当于把第行和第列连了一条双向边，就是经过了这个点就可以行列转换。所以我们可以考虑每一行压缩成一个点，每一列压缩成一个点，一共个点。点向点所在的行和列连两条容量为的有向边，然后点所在的行和列向也连两条容量为的有向边，之后每个o点就是行和列连容量为的双向边，跑最大流求最小割即可。这就是网络流经典的网格图转二分图trick.

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 504, M = 100005;
struct Edge{
    int to, nxt, w, cost;
}edge[M];
int h[N], cnt=1;
void add(int u, int v, int w, int x){
    edge[++cnt] = {v, h[u], w, x};
    h[u] = cnt;
}
void addedge(int u, int v, int w, int x){
    add(u, v, w, x), add(v, u, 0, -x);
}

int dis[N], vis[N];
int n, m, s, t;

bool spfa(){
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0, vis[s] = 1;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=h[u];i;i=edge[i].nxt){
            int v = edge[i].to;
            if(edge[i].w&&dis[v]>dis[u]+edge[i].cost){
                dis[v] = dis[u] + edge[i].cost;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }
        }
    }
    return dis[t] != 0x3f3f3f3f;
}

int ret = 0;

int cur[N];

int dfs(int u, int flow){
    if(u==t) return flow;
    int ans = 0;
    vis[u] = 1;
    for(int i=cur[u];i&&ans<flow;i=edge[i].nxt){
        int v = edge[i].to;
        cur[u] = i;
        if(edge[i].w&&!vis[v]&&dis[v]==dis[u]+edge[i].cost){
            int fl = dfs(v, min(edge[i].w, flow-ans));
            if(fl){
                ret += fl * edge[i].cost;
                edge[i].w -= fl;
                edge[i^1].w += fl;
                ans += fl;
            }
        }
    }
    vis[u] = 0;
    return ans;
}

int dinic(){
    int ans = 0;
    while(spfa()){
        memcpy(cur, h, sizeof h);
        int x = 0;
        while(x=dfs(s, 0x3f3f3f3f)) ans += x;
    }
    return ans;
}

int id(int linerow, int row){//L[1]~L[n]: 1~n, R[1]~R[m]: n+1~n+m
    return linerow + row*n;
}
char str[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    s = 0, t = n+m+1;
    
    for(int i=1;i<=n;i++){
        cin>>(str+1);
        for(int j=1;j<=m;j++){
            if(str[j]=='S'){
                addedge(s, id(i, 0), 0x3f3f3f3f, 0);
                addedge(s, id(j, 1), 0x3f3f3f3f, 0);
            }else if(str[j]=='T'){
                addedge(id(i, 0), t, 0x3f3f3f3f, 0);
                addedge(id(j, 1), t, 0x3f3f3f3f, 0);
            }else if(str[j]=='o'){
                addedge(id(i, 0), id(j, 1), 1, 0);
                addedge(id(j, 1), id(i, 0), 1, 0);
            }
        }
    }
    int ans = dinic();
    if(ans >=0x3f3f3f3f/2) cout<<"-1";
    else cout<<ans;
    return 0;
}

_を出力せよ！！！！_