spoj 839 最小割+二进制

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

#define inf 0x3fffffff

#define  N  550

struct node {

 int u,v,w,next;

}bian[N*20],ff[N*20],fk[N];

int vis[N];

int head[N],yong,dis[N],work[N];

int ans[N];

void init() {

yong=0;

memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w) {

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int bfs(int s,int t)

{

    memset(dis,-1,sizeof(dis));

    queue<int>q;

    q.push(s);

    dis[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=bian[i].next)

        {

            int v=bian[i].v;

            if(bian[i].w&&dis[v]==-1)

            {

                dis[v]=dis[u]+1;

                q.push(v);

                if(v==t)

                    return 1;

            }

        }

    }

    return 0;

}

int dfs(int  s,int limit,int t)

{

    if(s==t)return limit;

    for(int &i=work[s];i!=-1;i=bian[i].next)

    {

        int v=bian[i].v;

        if(bian[i].w&&dis[v]==dis[s]+1)

        {

            int tt=dfs(v,min(limit,bian[i].w),t);

            if(tt)

            {

                bian[i].w-=tt;

                bian[i^1].w+=tt;

                return tt;

            }

        }

    }

    return 0;

}

int dinic(int s,int t)

{

    int ans=0;

    while(bfs(s,t))

    {

        memcpy(work,head,sizeof(head));

        while(int tt=dfs(s,inf,t))

            ans+=tt;

    }

    return ans;

}

void build(int t,int m,int kk,int f) {

  init();

  int i;

  for(i=1;i<=m;i++) {

    addedge(ff[i].u,ff[i].v,1);

    addedge(ff[i].v,ff[i].u,1);

  }

  for(i=1;i<=kk;i++) {

    if(fk[i].v&(1<<f)) {

        addedge(0,fk[i].u,inf);

        addedge(fk[i].u,0,0);

    }

    else {

        addedge(fk[i].u,t,inf);

        addedge(t,fk[i].u,0);

    }

  }

  return ;

}

void dfs1(int u,int kk) {

   int i;

   vis[u]=1;

   for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(!vis[v]&&bian[i].w) {

        ans[v]|=(1<<kk);

        dfs1(v,kk);

    }

   }

   return ;

}

void print() {

 int i;

 for(i=0;i<yong;i++)

    printf("%d %d %d\n",bian[i].u,bian[i].v,bian[i].w);

}

int main() {

     int n,m,i,kk,t,k;

     scanf("%d",&t);

     while(t--) {

        scanf("%d%d",&n,&m);

        for(i=1;i<=m;i++)

            scanf("%d%d",&ff[i].u,&ff[i].v);

        scanf("%d",&kk);

        for(i=1;i<=kk;i++)

            scanf("%d%d",&fk[i].u,&fk[i].v);

        memset(ans,0,sizeof(ans));

        for(k=0;k<31;k++) {

            build(n+1,m,kk,k);

          //  print();break;

            dinic(0,n+1);

          // printf("%d\n",dinic(0,n+1));

            memset(vis,0,sizeof(vis));

            dfs1(0,k);

        }

        for(i=1;i<=n;i++)

            printf("%d\n",ans[i]);

     }

return 0;}
巴特西

spoj 839 最小割+二进制

最新文章

热门文章
