SPOJ NETADMIN_Smart Network Administrator

浏览数：14 / 时间：2015年06月09日

给一个图，某些点需要单独以某一种颜色的线连接到1点，问如何安排能够使得整个图颜色最多的一条路颜色最少。

显然，二分枚举然后加以颜色其实就是流量了，相当于对每条边限定一个当前二分的流量值，判断能否满流即可。

召唤代码君：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 555
#define maxm 333333
using namespace std;

const int inf=~0U>>2;
int to[maxm],next[maxm],c[maxm],first[maxm],edge;
int tag[maxn],d[maxn],TAG=520;
int Q[maxn],bot,top;
bool can[maxn];
int n,m,k,T,h,s,t,house,ans,boder;

void addedge(int U,int V)
{
    edge++;
    to[edge]=V,c[edge]=1,next[edge]=first[U],first[U]=edge;
    edge++;
    to[edge]=U,c[edge]=1,next[edge]=first[V],first[V]=edge;
}

void _input()
{
    scanf("%d%d%d",&n,&m,&k);
    edge=-1;
    for (int i=0; i<=n; i++) first[i]=-1;
    s=1,t=0,house=k;
    while (k--)
    {
        scanf("%d",&h);
        addedge(h,t);
    }
    boder=edge;
    while (m--)
    {
        scanf("%d%d",&k,&h);
        addedge(k,h);
    }
}

bool bfs()
{
    Q[bot=top=1]=t,d[t]=0,can[t]=false,tag[t]=++TAG;
    while(bot<=top)
    {
        int cur=Q[bot++];
        for (int i=first[cur]; i!=-1; i=next[i])
        {
            if (c[i^1]>0 && tag[to[i]]!=TAG)
            {
                tag[to[i]]=TAG,Q[++top]=to[i];
                d[to[i]]=d[cur]+1,can[to[i]]=false;
                if (to[i]==s) return true;
            }
        }
    }
    return false;
}

int dfs(int cur,int num)
{
    if (cur==t) return num;
    int tmp=num,k;
    for (int i=first[cur]; i!=-1; i=next[i])
        if (c[i]>0 && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && !can[to[i]])
        {
            k=dfs(to[i],min(num,c[i]));
            if (k) num-=k,c[i]-=k,c[i^1]+=k;
            if (num==0) break;
        }
    if (num) can[cur]=true;
    return tmp-num;
}

bool check(int x)
{
    for (int i=0; i<=boder; i++) c[i]=1;
    for (int i=boder+1; i<=edge; i++) c[i]=x;
    for ( ans=0; bfs(); ) ans+=dfs(s,inf);
    return ans>=house;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        _input();
        int l=1,r=n,mid;
        while (l<r)
        {
            mid=(l+r)>>1;
            if (check(mid)) r=mid;
                else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}