UVA, 563 Crimewave

제목: 단체 가 모든 은행 을 빼 앗 은 후에 S * A 매트릭스 밖으로 철수 하면 빠 져 나 가도 한 점 에 두 번 가지 못 하도록 요구 하고 완전히 탈출 할 수 있 는 지 물 어보 세 요.
이 문 제 는 가장 큰 흐름 문제 로 주로 그림 을 구축 한 다음 에 최대 흐름 알고리즘 으로 은행 수량 과 탈출 수량 이 같 는 지 여 부 를 알 아 내 는 것 이다.그림 을 어떻게 구축 합 니까?주로 철거 점 으로 한 점 을 두 점 으로 나 누 는데 점 (i, j) 은 앞 점 (i - 1) * A + j, 뒤 점 (i - 1) * A + j + M (M 은 비교적 큰 숫자 로 M 이 S * A 보다 크 면 된다) 이 라 고 할 수 있다. 그리고 앞 점 과 뒤 점 을 연결 하고 방향 은 앞 에서 뒤 이다.
인접 한 점, 그림 은 방향 이 없 으 며 이 점 의 뒤 점 으로 인접 점 의 앞 점 을 연결 합 니 다.마지막 으로 하나의 슈퍼 소스 로 모든 은행 점 의 앞 점 을 연결 하고 하나의 슈퍼 종점 으로 모든 가장자리 점 의 뒤 점 을 연결 하 며 모든 변 의 가중치 가 1 이 고 그림 이 구축 되 었 다.그리고 익숙 한 최대 흐름 알고리즘 으로
Ford - Fulkerson 최대 흐름 알고리즘 코드 참조:http://blog.csdn.net/itaskyou/article/details/51331344

#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
#define N 5005
#define INF 1000000
int q[4][2]= {1,0,0,1,-1,0,0,-1};
struct edge
{
    int to,cap,rev;
    edge(int a,int b,int c)
    {
        to=a;
        cap=b;
        rev=c;
    }
};
vector<edge>v[N];
void add_edge(int from,int to,int cap);
int dfs(int a,int t,int f);
int max_flow(int s,int t);
int used[N];
int vis[60][60];
int m,n,num;
int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int a,b,c,d;
        cin>>m>>n>>num;
       // memset(vis,0,sizeof(vis));
        for(int i=0; i<N; i++)
            v[i].clear();
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                add_edge((i-1)*n+j,(i-1)*n+j+m*n,1);//            
                for(int k=0; k<4; k++)//     
                {
                    int k1=i+q[k][0];
                    int k2=j+q[k][1];
                    if(k1>0&&k1<=m&&k2>0&&k2<=n)
                    {
                        add_edge((i-1)*n+j+m*n,(k1-1)*n+k2,1);
                    }
                }
            }
        }

        for(int i=0; i<num; i++)//      for                 。
        {
            cin>>c>>d;
            add_edge(0,(c-1)*n+d,1);
        }
        for(int i=1; i<=n; i++)
        {
            add_edge(i+m*n,m*n*2+1,1);
        }
        if(m>1)
        {
            for(int i=1; i<=n; i++)
            {
                add_edge(i+(m-1)*n+m*n,m*n*2+1,1);
            }
        }
        for(int i=2; i<m; i++)
            add_edge((i-1)*n+1+m*n,m*n*2+1,1);

        if(n>1)
        {
            for(int i=2; i<m; i++)
                add_edge(i*n+m*n,m*n*2+1,1);
        }
        int ans=max_flow(0,m*n*2+1);
     //   cout<<ans;
        if(ans==num)
            cout<<"possible
";
        else
            cout<<"not possible
";
    }
    return 0;
}

void add_edge(int from,int to,int cap)
{
    v[from].push_back(edge(to,cap,v[to].size()));
    v[to].push_back(edge(from,0,v[from].size()-1));
}
int dfs(int a,int t,int f)
{
    if(a==t)
        return f;
    used[a]=1;
    for(int i=0; i<v[a].size(); i++)
    {
        edge &e=v[a][i];
        if(!used[e.to]&&e.cap>0)
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap-=d;
                v[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t)
{
    int flow=0;
    while(1)
    {
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0)
            return flow;
        flow+=f;
    }
}