Internship – ZOJ 2532 – 割边

来源: Internship – ZOJ 2532 – Virtual Judge

题目大意:有N个城市,M个中转站以及L条有向边(u, v, c),表示可以从u向v传送信息,带宽为c。每个城市都在向CIA总部发送无穷大的信息量,但是目前总部实际接收带宽已经不能满足要求。CIA决定要增大某条边的带宽以增大总部的接收带宽,请找出哪些边带宽的增加能导致总部接收带宽的增加。(1 <= N+M <= 100, 1 <= L <= 1000)

解题思路:dinic求割边模板,题意就是要求有向图的割边,也就是说如果这条边增加流量就可以再延伸出增广路来的边。解法是先跑一边dinic然后分别正着,反着跑一边dfs,将还有残余流量的边的端点标记后遍历边去找割边就好了。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=200;
const int E=5000;
int vis[N],flag[N];

int cnt,head[N],dep[N],cur[N];

struct node
{
    int x,y;
    int nxt;
    int c;
}edge[E];

void addedge(int u,int v,int w)
{
    edge[cnt].x=u;
    edge[cnt].y=v;
    edge[cnt].c=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;

    edge[cnt].x=v;
    edge[cnt].y=u;
    edge[cnt].c=0;
    edge[cnt].nxt=head[v];
    head[v]=cnt++;
}

bool bfs(int s,int t)
{
    memset(dep,0,sizeof(dep));
    queue<int>q;
    while(!q.empty())
    {
        q.pop();
    }
    memcpy(cur,head,sizeof(head));
    dep[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=edge[i].nxt)
        {
            if(!dep[edge[i].y]&&edge[i].c)
            {
                dep[edge[i].y]=dep[now]+1;
                q.push(edge[i].y);
            }
        }
    }
    return dep[t];
}

int dfs(int now,int t,int limit)
{
    if(!limit||now==t)
        return limit;
    int flow=0,f;
    for(int i=cur[now];i!=-1;i=edge[i].nxt)
    {
        cur[now]=i;
        if(dep[edge[i].y]==dep[now]+1&&
           (f=dfs(edge[i].y,t,min(limit,edge[i].c))))
        {
            flow+=f;
            limit-=f;
            edge[i].c-=f;
            edge[i^1].c+=f;
            if(!limit)break;
        }
    }
    if(!flow)dep[now]=0;
    return flow;
}

void dinic(int s,int t)
{
    while(bfs(s,t))
    {
        dfs(s,t,inf);
    }
}

void dfsa(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int y=edge[i].y;
        if(vis[y]==0&&edge[i].c)
        {
            dfsa(y);
        }
    }
}

void dfsb(int u)
{
    flag[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int y=edge[i].y;
        if(edge[i^1].c&&flag[y]==0)
        {
            dfsb(y);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n,m,l;
    int x,y,c;
    int ans[E];
    while(cin>>n>>m>>l)
    {
        if(!n)break;
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=l;i++)
        {
            cin>>x>>y>>c;
            addedge(x,y,c);
        }
        for(int i=1;i<=n;i++)
        {
            addedge(n+m+1,i,inf);
        }
        dinic(n+m+1,0);
        memset(vis,0,sizeof(vis));
        memset(flag,0,sizeof(flag));
        dfsa(n+m+1);
        dfsb(0);
        int k=0;
        for(int i=0;i<cnt;i+=2)
        {
            x=edge[i].x;
            y=edge[i].y;
            if(vis[x]==1&&flag[y]==1&&edge[i].c==0)
            {
                ans[k++]=i/2+1;
            }
        }
        if(k==0)
        {
            cout<<endl;
        }
        else
        {
            cout<<ans[0];
            for(int i=1;i<k;i++)
            {
                cout<<" "<<ans[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注