HDU 3491 Thieves (SAP)

Thieves

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1014    Accepted Submission(s): 456

Problem Description

In the kingdom of Henryy, there are N (2 <= N <= 100) cities, with M (M <= 10000) two-direct ways connecting them.
A group of thieves from abroad plan to steal the metropolitan museum in city H (It has not been demolished). However, the brave, brilliant, bright police in the kingdom have known this plan long before, and they also plan to catch the thieves. The thieves are in the city S at present. The police try to catch them on their way from S to H. Although the thieves might travel this way by more than one group, our excellent police has already gather the statistics that the number of the people needed in city I (1<=I<=N) to arrest the thieves.
The police do not want to encounter the thieves in either city S or city H.
The police finish the task with the minimum number of people. Do you know the exact number?

 

 

Input

The first line contains an integer T (T <= 10), indicating the number of the test cases.
The first line of each test case has four integers: N, the number of the cities; M, the number of the roads; S (1<=S<=N), the label of city S; H (1<=T<=N, S≠H), the label of city H.
The second line contains N integers, indicating the number of people needed in each city. The sum of these N integers is less than 10000.
Then M lines followed, each containing two integers x and y, indicating that there is a two-direct roads between city x and y. Notices that no road between city S and H.
A blank line is followed after each test case.

 

 

Output

For each test case, output a single integer in a separate line, indicating the minimum number of people the police used.

 

 

Sample Input

1 5 5 1 5 1 6 6 11 1 1 2 1 3 2 4 3 4 4 5

 

 

Sample Output

11

 

 

Source

2010 ACM-ICPC Multi-University Training Contest（6）——Host by BIT

 

 

Recommend

zhouzeyong

 

 

 

题意：
有一群盗贼要从s城出发去h城，现在告诉你一共有n个城，m条路，每一个城都要派一定的人去把守，现在问你一共要多少人才能堵住盗贼，使之不能从s城到h城，并前要求你不能在s城和h城拦截盗贼。
这是一个最小割的模板题，首先我们把每个城i拆成两个城i和i+n，权值为他需要把守的人数，s到s+n和h到h+n拆点后权值为inf，因为题目要求不能在s城和h城拦截盗贼，两个城之间的路连一条边，权值为正无穷，根据最小割=最大流，跑一遍最大流即可。

 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int VM=1010;
const int EM=50010;
const int INF=0x3f3f3f3f;

struct Edge{
    int to,nxt;
    int cap;
}edge[EM<<1];

int n,m,s,h,cnt,head[VM];
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];

void addedge(int cu,int cv,int cw){
    edge[cnt].to=cv;  edge[cnt].cap=cw;  edge[cnt].nxt=head[cu];
    head[cu]=cnt++;
    edge[cnt].to=cu;  edge[cnt].cap=0;   edge[cnt].nxt=head[cv];
    head[cv]=cnt++;
}

int src,des;

int SAP(int n){
    int max_flow=0,u=src,v;
    int id,mindep;
    aug[src]=INF;
    pre[src]=-1;
    memset(dep,0,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=n;
    for(int i=0;i<=n;i++)
        cur[i]=head[i]; // 初始化当前弧为第一条弧
    while(dep[src]<n){
        int flag=0;
        if(u==des){
            max_flow+=aug[des];
            for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
                id=cur[v];
                edge[id].cap-=aug[des];
                edge[id^1].cap+=aug[des];
                aug[v]-=aug[des];   // 修改可增广量，以后会用到
                if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
                    u=v;
            }
        }
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].to;    // 从当前弧开始查找允许弧
            if(edge[i].cap>0 && dep[u]==dep[v]+1){  // 找到允许弧
                flag=1;
                pre[v]=u;
                cur[u]=i;
                aug[v]=min(aug[u],edge[i].cap);
                u=v;
                break;
            }
        }
        if(!flag){
            if(--gap[dep[u]]==0)    /* gap优化，层次树出现断层则结束算法 */
                break;
            mindep=n;
            cur[u]=head[u];
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                v=edge[i].to;
                if(edge[i].cap>0 && dep[v]<mindep){
                    mindep=dep[v];
                    cur[u]=i;   // 修改标号的同时修改当前弧
                }
            }
            dep[u]=mindep+1;
            gap[dep[u]]++;
            if(u!=src)  // 回溯继续寻找允许弧
                u=pre[u];
        }
    }
    return max_flow;
}

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d",&n,&m,&s,&h);
        cnt=0;
        memset(head,-1,sizeof(head));
        src=0; des=2*n+1;
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(i!=s && i!=h)
                addedge(i,n+i,x);
        }
        addedge(src,s,INF);
        addedge(s,n+s,INF);
        addedge(h,n+h,INF);
        addedge(n+h,des,INF);
        int u,v;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            addedge(n+u,v,INF);
            addedge(n+v,u,INF);
        }
        printf("%d\n",SAP(des+1));
    }
    return 0;
}