CodeForcesGym 100517H Hentium Scheduling

Hentium Scheduling

Time Limit: 2000ms

Memory Limit: 262144KB

This problem will be judged on CodeForcesGym. Original ID: 100517H
64-bit integer IO format: %I64d Java class name: (Any)

解题：我擦，裸的网络流啊，居然没发现

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL INF = 0x3f3f3f3f3f3f3f3f;
 5 const int maxn = 210;
 6 struct arc {
 7     int to,next;
 8     LL flow;
 9     arc(int x = 0,LL y = 0,int z = -1) {
10         to = x;
11         flow = y;
12         next = z;
13     }
14 } e[2000010];
15 int head[maxn],d[maxn],cur[maxn],tot,S,T;
16 void add(int u,int v,LL flow) {
17     e[tot] = arc(v,flow,head[u]);
18     head[u] = tot++;
19     e[tot] = arc(u,0,head[v]);
20     head[v] = tot++;
21 }
22 bool bfs() {
23     queue<int>q;
24     memset(d,-1,sizeof d);
25     d[S] = 1;
26     q.push(S);
27     while(!q.empty()) {
28         int u = q.front();
29         q.pop();
30         for(int i = head[u]; ~i; i = e[i].next) {
31             if(e[i].flow && d[e[i].to] == -1) {
32                 d[e[i].to] = d[u] + 1;
33                 q.push(e[i].to);
34             }
35         }
36     }
37     return d[T] > -1;
38 }
39 LL dfs(int u,LL low) {
40     if(u == T) return low;
41     LL a,tmp = 0;
42     for(int &i = cur[u]; ~i; i = e[i].next) {
43         if(e[i].flow && d[e[i].to] == d[u]+1&&(a=dfs(e[i].to,min(low,e[i].flow)))) {
44             e[i].flow -= a;
45             e[i^1].flow += a;
46             low -= a;
47             tmp += a;
48             if(!low) break;
49         }
50     }
51     if(!tmp) d[u] = -1;
52     return tmp;
53 }
54 LL dinic(LL ret = 0) {
55     while(bfs()) {
56         memcpy(cur,head,sizeof head);
57         ret += dfs(S,INF);
58     }
59     return ret;
60 }
61 bool vis[maxn];
62 void dfs(int u) {
63     vis[u] = true;
64     for(int i = head[u]; ~i; i = e[i].next)
65         if(e[i].flow && !vis[e[i].to]) dfs(e[i].to);
66 }
67 int main() {
68 #define NAME "hentium"
69     freopen(NAME".in","r",stdin);
70     freopen(NAME".out","w",stdout);
71     int n,a,b;
72     while(scanf("%d",&n),n) {
73         memset(head,-1,sizeof head);
74         S = tot = 0;
75         T = n + 1;
76         for(int i = 1; i <= n; ++i) {
77             scanf("%d%d",&a,&b);
78             add(S,i,a);
79             add(i,T,b);
80         }
81         for(int i = 1; i <= n; ++i)
82             for(int j = 1; j <= n; ++j) {
83                 scanf("%d",&a);
84                 if(a) add(i,j,a);
85             }
86         printf("%I64d
",dinic());
87         memset(vis,false,sizeof vis);
88         dfs(S);
89         for(int i = 1; i <= n; ++i)
90             printf("%d%c",vis[i]?2:1,i == n?'
':' ');
91     }
92     return 0;
93 }

View Code