游戏

横的联通快为入，竖的为出。

样例的图就像这样：

S->a1,a2,a3,a4,a5

a1->2,3,4　　a2->5　　a3->7,8　　a4->9,10　　a5->12

5,9->b1　　2->b2　　10->b3　　3,7->b4　　4,8,12->b5

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e4+10;
int n,m,cnt;
int g[100][100];
int beg[maxn],nex[maxn],to[maxn],w[maxn],e;
inline void add(int x,int y,int z){
    nex[e]=beg[x];beg[x]=e;
    to[e]=y;w[e]=z;e++;
}
int dep[maxn];
queue<int>q;
inline int bfs(){
    memset(dep,0x3f,sizeof(dep));
    while(!q.empty())q.pop();
    dep[0]=0;
    q.push(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=beg[x];~i;i=nex[i]){
            int t=to[i];
            if(w[i]&&dep[t]>5000){
                dep[t]=dep[x]+1;
                q.push(t);
            }
        }
    }
    return dep[5000]<=5000;
}
inline int dfs(int x,int lim){
    if(x==5000||!lim)return lim;
    int ans=0;
    for(int i=beg[x];~i;i=nex[i]){
        int t=to[i];
        if(dep[t]==dep[x]+1){
            int f=dfs(t,min(lim,w[i]));
            ans+=f;lim-=f;
            w[i]-=f;w[i^1]+=f;
        }
    }
    return ans;
}
int main(){
    memset(beg,-1,sizeof(beg));
    cin>>n>>m;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++){
            if(s[j-1]=='*')g[i][j]=1;
            if(s[j-1]=='x')g[i][j]=2;
            if(s[j-1]=='#')g[i][j]=3;
        }
    }
    cnt=n*m;
    for(int i=1;i<=n;i++){
        cnt++;
        add(0,cnt,1);
        add(cnt,0,0);
        for(int j=1;j<=m;j++){
            if(g[i][j]==1){
                add(cnt,(i-1)*m+j,inf);
                add((i-1)*m+j,cnt,0);
            }
            if(g[i][j]==2)continue;
            if(g[i][j]==3){
                cnt++;
                add(0,cnt,1);
                add(cnt,0,0);
            }
        }
    }
    for(int i=1;i<=m;i++){
        cnt++;
        add(cnt,5000,1);
        add(5000,cnt,0);
        for(int j=1;j<=n;j++){
            if(g[j][i]==1){
                add((j-1)*m+i,cnt,inf);
                add(cnt,(j-1)*m+i,0);
            }
            if(g[j][i]==2)continue;
            if(g[j][i]==3){
                cnt++;
                add(cnt,5000,1);
                add(5000,cnt,0);
            }
        }
    }
    int maxflow=0;
    while(bfs())maxflow+=dfs(0,inf);
    printf("%d
",maxflow);
    return 0;
}

深深地感到自己的弱小。