首页 > 代码库 > SPOJ NETADMIN_Smart Network Administrator

SPOJ NETADMIN_Smart Network Administrator

2024-07-13 05:27:14   223人阅读

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

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

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 555#define maxm 333333using 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;}


联系
我们