网络流24题——试题库问题

1 #include
2 #define N 100010
3 #define inf 2147483647
4 #define ll long long
5 using namespace std;
6 int q[N];
7 int n,k,cnt,st,t,m;
8 int dis[200000],ans,head[N];
9 bool vis[200000];
10 struct node
11 {
12 int nex,to,val;
13 }e[N];
14
15 void add(int x,int y,int z)
16 {
17 e[++cnt].nex=head[x];
18 e[cnt].to=y;
19 e[cnt].val=z;
20 head[x]=cnt;
21 }
22
23 void ins(int x,int y,int z)
24 {
25 add(x,y,z);add(y,x,0);
26 }
27
28 bool bfs()
29 {
30 memset(dis,-1,sizeof(dis));
31 int l=0,r=1,u;
32 q[0]=dis[0]=0;
33 while (l<r)
34 {
35 u=q[l++];
36 for (int i=head[u];i;i=e[i].nex)
37 {
38 int ne=e[i].to;
39 if (dis[ne]==-1&&e[i].val)
40 {
41 q[r++]=ne;
42 dis[ne]=dis[u]+1;
43 }
44 }
45 }
46 if (dis[t]==-1) return false;
47 return true;
48 }
49
50 int dfs(int u,int flow)
51 {
52 int w,used=0;
53 if (u==t) return flow;
54 for (int i=head[u];i;i=e[i].nex)
55 {
56 int ne=e[i].to;
57 if (dis[ne]==dis[u]+1&&e[i].val)
58 {
59 w=flow-used;
60 w=dfs(ne,min(w,e[i].val));
61 e[i].val-=w,e[i^1].val+=w;
62 used+=w;
63 if (used==flow) return flow;
64 }
65 }
66 if (!used) dis[u]=-1;
67 return used;
68 }
69
70 void dinic()
71 {
72 while (bfs())
73 ans+=dfs(st,inf);
74 }
75 int main()
76 {
77 scanf("%d%d",&k,&n);
78 st=0,t=8001;
79 for (int i=1;i<=k;i++)
80 {
81 int x;
82 scanf("%d",&x);
83 ins(st,i,x);
84 m+=x;
85 }
86 for (int i=1;i<=n;i++)
87 {
88 int ty;
89 scanf("%d",&ty);
90 for (int j=1;j<=ty;j++)
91 {
92 int tmp;
93 scanf("%d",&tmp);
94 ins(tmp,i+k,1);
95 }
96 ins(i+k,t,1);
97 }
98 dinic();
99 if (ans==m)
100 {
101 for (int i=1;i<=k;i++)
102 {
103 printf("%d: ",i);
104 for (int j=head[i];j;j=e[j].nex)
105 {
106 if (e[j].to>0&&!e[j].val)
107 printf("%d ",e[j].to-k);
108 }
109 cout<<endl;
110 }
111 }
112 else printf("No Solution!\n");
113 return 0;
114 }