SPOJOPTMOptimalMarks

  1 #include 
  2 using namespace std;
  3 const int INF = ~0U>>2;
  4 const int maxn = 510;
  5 struct arc{
  6     int to,flow,next;
  7     arc(int x = 0,int y = 0,int z = -1){
  8         to = x;
  9         flow = y;
 10         next = z;
 11     }
 12 }e[maxn*maxn];
 13 int head[maxn],gap[maxn],d[maxn],S,T,tot;
 14 void add(int u,int v,int flow){
 15     e[tot] = arc(v,flow,head[u]);
 16     head[u] = tot++;
 17     e[tot] = arc(u,0,head[v]);
 18     head[v] = tot++;
 19 }
 20 void bfs(){
 21     queue<int>q;
 22     memset(gap,0,sizeof gap);
 23     memset(d,-1,sizeof d);
 24     q.push(T);
 25     d[T] = 0;
 26     while(!q.empty()){
 27         int u = q.front();
 28         q.pop();
 29         ++gap[d[u]];
 30         for(int i = head[u]; ~i; i = e[i].next){
 31             if(e[i^1].flow && d[e[i].to] == -1){
 32                 d[e[i].to] = d[u] + 1;
 33                 q.push(e[i].to);
 34             }
 35         }
 36     }
 37 }
 38 int sap(int u,int low){
 39     if(u == T) return low;
 40     int tmp = 0,a,minH = T - 1;
 41     for(int i = head[u]; ~i; i = e[i].next){
 42         if(e[i].flow){
 43             if(d[u] == d[e[i].to] + 1){
 44                 a = sap(e[i].to,min(low,e[i].flow));
 45                 if(!a) continue;
 46                 e[i].flow -= a;
 47                 e[i^1].flow += a;
 48                 low -= a;
 49                 tmp += a;
 50                 if(!low) break;
 51             }
 52             minH = min(minH,d[e[i].to]);
 53             if(d[S] >= T) return tmp;
 54         }
 55     }
 56     if(!tmp){
 57         if(--gap[d[u]] == 0) d[S] = T;
 58         ++gap[d[u] = minH + 1];
 59     }
 60     return tmp;
 61 }
 62 int maxflow(int ret = 0){
 63     bfs();
 64     while(d[S]  sap(S,INF);
 65     return ret;
 66 }
 67 int n,m,k,mark[maxn],con[maxn];
 68 bool mp[maxn][maxn],vis[maxn];
 69 void build(int x){
 70     S = n + 1;
 71     T = S + 1;
 72     memset(head,-1,sizeof head);
 73     memset(vis,false,sizeof vis);
 74     tot = 0;
 75     for(int i = 0; i i){
 76         if((mark[con[i]]>>x)&1) add(S,con[i],INF);
 77         else add(con[i],T,INF);
 78     }
 79     for(int i = 1; i <= n; ++i)
 80         for(int j = 1; j <= n; ++j)
 81             if(mp[i][j]) add(i,j,1);
 82 }
 83 void dfs(int u,int x){
 84     vis[u] = true;
 85     mark[u] |= (1<<x);
 86     for(int i = head[u]; ~i; i = e[i].next)
 87         if(!vis[e[i].to] && e[i].flow) dfs(e[i].to,x);
 88 }
 89 int main(){
 90     int kase,u,v;
 91     scanf("%d",&kase);
 92     while(kase--){
 93         scanf("%d%d",&n,&m);
 94         memset(mark,0,sizeof mark);
 95         memset(mp,false,sizeof mp);
 96         for(int i = 0; i i){
 97             scanf("%d%d",&u,&v);
 98             mp[u][v] = mp[v][u] = true;
 99         }
100         scanf("%d",&k);
101         for(int i = 0; i i){
102             scanf("%d%d",&u,&v);
103             mark[u] = v;
104             con[i] = u;
105         }
106         for(int i = 0; i <32; ++i){
107             build(i);
108             maxflow();
109             dfs(S,i);
110         }
111         for(int i = 1; i <= n; ++i)
112             printf("%d\n",mark[i]);
113     }
114     return 0;
115 }