【LYOI 212】「雅礼集训 2017 Day8」价（二分匹配+最大权闭合子图）

「雅礼集训 2017 Day8」价

内存限制: 512 MiB时间限制: 1000 ms

输入文件: z.in输出文件: z.out

　　就是这样证明吧？

　　其实虽然我不会推出结论，但是这题的key的位置实在太明显了，脑洞再大一点就好了。毕竟这种题是证明还好，但是比较难以直接想到结论的。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 310
  9 #define INF 0xfffffff
 10 // #define LL long long
 11 
 12 int mymin(int x,int y) {return x<y?x:y;}
 13 int n;
 14 
 15 struct node
 16 {
 17     int x,y,next,f,o;
 18 }t[Maxn*Maxn*2];
 19 int first[Maxn],len;
 20 
 21 void ins(int x,int y,int f)
 22 {
 23     if(x==y) return;
 24     t[++len].x=x;t[len].y=y;t[len].f=f;
 25     t[len].next=first[x];first[x]=len;t[len].o=len+1;
 26     t[++len].x=y;t[len].y=x;t[len].f=0;
 27     t[len].next=first[y];first[y]=len;t[len].o=len-1;
 28 }
 29 
 30 queue<int > q;
 31 int dis[Maxn],st,ed;
 32 bool bfs()
 33 {
 34     while(!q.empty()) q.pop();
 35     memset(dis,-1,sizeof(dis));
 36     q.push(st);dis[st]=0;
 37     while(!q.empty())
 38     {
 39         int x=q.front();
 40         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 41         {
 42             int y=t[i].y;
 43             if(dis[y]==-1)
 44             {
 45                 dis[y]=dis[x]+1;
 46                 q.push(y);
 47             }
 48         }
 49         q.pop();
 50     }
 51     return dis[ed]!=-1;
 52 }
 53 
 54 int ffind(int x,int flow)
 55 {
 56     if(x==ed) return flow;
 57     int now=0;
 58     for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 59     {
 60         int y=t[i].y;
 61         if(dis[y]==dis[x]+1)
 62         {
 63             int a=ffind(y,mymin(flow-now,t[i].f));
 64             t[i].f-=a;
 65             t[t[i].o].f+=a;
 66             now+=a;
 67         }
 68         if(now==flow) break;
 69     }
 70     if(now==0) dis[x]=-1;
 71     return now;
 72 }
 73 
 74 int ans=0;
 75 void max_flow()
 76 {
 77     while(bfs())
 78     {
 79         ans-=ffind(st,INF);
 80     }
 81 }
 82 
 83 void output()
 84 {
 85     for(int i=1;i<=len;i+=2)
 86     {
 87         printf("%d -> %d %d
",t[i].x,t[i].y,t[i].f);
 88     }
 89 }
 90 
 91 
 92 //-------------------------
 93 int match[Maxn],chw[Maxn],g[Maxn][Maxn];
 94 bool ffind2(int x,int nt)
 95 {
 96     for(int i=1;i<=g[x][0];i++)
 97     {
 98         int y=g[x][i];
 99         if(chw[y]!=nt)
100         {
101             chw[y]=nt;
102             if(!match[y]||ffind2(match[y],nt))
103             {
104                 match[y]=x;
105                 return 1;
106             }
107         }
108     }
109     return 0;
110 }
111 
112 void get_match()
113 {
114     memset(chw,0,sizeof(chw));
115     memset(match,0,sizeof(match));
116     int nt=0;
117     for(int i=1;i<=n;i++)
118     {
119         ffind2(i,++nt);
120     }
121 }
122 
123 //-------------------------
124 
125 
126 int main()
127 {
128     scanf("%d",&n);
129     st=n+1;ed=st+1;
130     bool ok=1;int sm=0;
131     for(int i=1;i<=n;i++)
132     {
133         int x;
134         scanf("%d",&x);
135         g[i][0]=x;
136         for(int j=1;j<=x;j++)
137         {
138             int y;
139             scanf("%d",&y);
140             g[i][j]=y;
141             // ins(i,y,INF);
142         }
143     }
144     get_match();
145     // for(int i=1;i<=n;i++) printf("%d ",match[i]);printf("
");
146     for(int i=1;i<=n;i++)
147      for(int j=1;j<=g[i][0];j++)
148      {
149          ins(i,match[g[i][j]],INF);
150      }
151     for(int i=1;i<=n;i++)
152     {
153         int w;
154         scanf("%d",&w);
155         w=-w;
156         if(w>0) {ans+=w;ins(st,i,w);}
157         else ins(i,ed,-w);
158     }
159     // output();
160     max_flow();
161     printf("%d
",-ans);
162     return 0;
163 }

View Code

2017-04-09 21:36:14