Smallest Minimum Cut

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 740 Accepted Submission(s): 285

Problem Description

Consider a network

G=(V,E) with source

s and sink

t. An s-t cut is a partition of nodes set

V into two parts such that

s and

t belong to different parts. The cut set is the subset of

E with all edges connecting nodes in different parts. A minimum cut is the one whose cut set has the minimum summation of capacities. The size of a cut is the number of edges in the cut set. Please calculate the smallest size of all minimum cuts.

Input

The input contains several test cases and the first line is the total number of cases

T (1≤T≤300).
Each case describes a network

G, and the first line contains two integers

n (2≤n≤200) and

m (0≤m≤1000) indicating the sizes of nodes and edges. All nodes in the network are labelled from

1 to

n.
The second line contains two different integers

s and

t (1≤s,t≤n) corresponding to the source and sink.
Each of the next

m lines contains three integers

u,v and

w (1≤w≤255) describing a directed edge from node

u to

v with capacity

Output

For each test case, output the smallest size of all minimum cuts in a line.

Sample Input

   24 51 41 2 31 3 12 3 12 4 13 4 24 51 41 2 31 3 12 3 12 4 13 4 3 
 

Sample Output

23

题目大意：

给出一个有N个点，M条边的网络图，让我们求最小割条件下最小割边数。

思路：

我们将所有边权*w+1然后跑最小割最大流即可。

Maxflow%w就是答案。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
    int from;
    int to;
    int w;
    int next;
}e[160000];
int cur[1500];
int head[1500];
int divv[1500];
int cont,ss,tt;
void add(int from,int to,int w)
{
    e[cont].from=from;
    e[cont].w=w;
    e[cont].to=to;
    e[cont].next=head[from];
    head[from]=cont++;
}
int n,m;
int makedivv()
{
    memset(divv,0,sizeof(divv));
    divv[ss]=1;
    queue<int >s;
    s.push(ss);
    while(!s.empty())
    {
        int u=s.front();
        if(u==tt)return 1;
        s.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int w=e[i].w;
            int v=e[i].to;
            if(divv[v]==0&&w)
            {
                divv[v]=divv[u]+1;
                s.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int u,int maxflow,int tt)
{
    if(u==tt)return maxflow;
    int ret=0;
    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        int w=e[i].w;
        if(divv[v]==divv[u]+1&&w)
        {
            int f=Dfs(v,min(maxflow-ret,w),tt);
            e[i].w-=f;
            e[i^1].w+=f;
            ret+=f;
            if(ret==maxflow)return ret;
        }
    }
    return ret;
}
void Dinic()
{
    long long int ans=0;
    while(makedivv()==1)
    {
        memcpy(cur,head,sizeof(head));
        ans+=Dfs(ss,0x3f3f3f3f,tt);
    }
    printf("%lld\n",ans%100000);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        scanf("%d%d",&ss,&tt);
        cont=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            z=z*100000+1;
            add(x,y,z);add(y,x,0);
        }
        Dinic();
    }
}

秒客网

Hdu 6214 Smallest Minimum Cut【Dinic-最大流最小割】

Smallest Minimum Cut

相关文章