2016.2.21
01 飞行员配对方案问题（习题 8-10）
每一条边连接外籍-国内飞行员，显然是一个二分图，最多出发的飞机数，对应着最多的边匹配。
问题转化为经典的二分图匹配问题，可以用匈牙利或者网络流。
源点和每一个外籍飞行员、每一个国内飞行员和汇点、每个可行的配合之间连接一条容量为1的有向边。
可以派出的最多飞机数就是这个网络的最大流
建图部分代码
1 for(;;){2 int a,b,c;3 a=read();b=read();4 if(a==-1&&b==-1) break;5 insert(a,b,1);6 }7 for(int i=1;i<=m;i++) insert(n+1,i,1);8 for(int i=m+1;i<=n;i++) insert(i,n+2,1); 对于方案。。其实我们可以在增广的时候做标记的，但是反正比较懒套个模板嘛~
在时候枚举一下飞行员之间边，如果他的容量被修改为0了。那么这就是一对一对
1 for(int i=1;i<=m;i++){2 for(int j=last[i];j;j=e[j].next){3 if(e[j].cap==0&&e[j].to<=n&&e[j].to>=1){4 printf("%d %d\n",i,e[j].to);5 break;6 }7 }8 }//2016.2.21 02 太空飞行计划问题
大概想了一下，连接实验和所需的实验器材，容量是inf,连接源点和每个实验，容量是实验经费，连接器材和汇点，容量是器材费用
然后算算好像答案是这个网络的最小割？写个最小割就好了
考虑对于每个实验，如果这个子图的割在器材-汇之间，说明他是赚钱的，否则是赔钱的（好像不太对？想不出证明） 2016.2.21
2016.2.22 答案是所有赞助商给的经费-最小割
懒得处理输入了，假装每行有一个0做结束标志。
1 scanf("%d %d",&m,&n); 2 for(int i=1;i<=m;i++){ 3 scanf("%d",&p[i]); 4 int a;sum+=p[i]; 5 while(scanf("%d",&a),a) 6 insert(i,a+m,inf); 7 } 8 for(int i=1;i<=n;i++) {scanf("%d",&c[i]);} 9 s=n+m+1;t=n+m+2;10 for(int i=1;i<=m;i++) insert(s,i,p[i]);11 for(int i=1;i<=n;i++) insert(m+i,t,c[i]);12 int tp=dinic(s,t);13 printf("%d",sum-tp); *净收入=赞助费-成本 细思恐极
2016.2.29 还要输出方案。。把实验和仪器分开，不和t联通的实验被选中，器材同理。
2333我突然想起来dinic的bfs可以判联通移动
1 int tp=dinic(s,t); 2 for(int i=1;i<=m;i++){ 3 if(!bfs(i,t)){ 4 printf("%d ",i); 5 } 6 } putchar('\n'); 7 for(int i=1;i<=n;i++){ 8 if(!bfs(m+i,t)){ 9 printf("%d ",i);10 }11 } 12 printf("\n%d",sum-tp);
03 最小路径覆盖问题
我一看题目，诶 最小生成树？哎哟有向图
诶我靠可以写最小生成树
诶不对看错题目了
那么我们设 V={1，2，3... n}，构造网络 G1=(V1,E1)如下：
V1 = { x0 , x1,, xn}∪{ y0 , y1,, yn}，
E1 = {(x0 , xi )} ∪{( yi , y0 )}∪{(xi , yj )} (i. j)∈ E}
每条边容量都是1，求x0 y0的最大流
G1最大流也就是他的最大匹配数
最小路径覆盖=总节点数-最大匹配数 我们可以轻易的解决这个问题
1 s=n+n+1;t=n+n+2;2 for(int i=1;i<=n;i++){3 insert(s,i,1);4 insert(n+i,t,1);5 }6 for(int i=1;i<=m;i++){7 insert(edge[i][1],edge[i][2]+n,1);8 }9 printf("%d",n-dinic(s,t)); 2016.2.22输出路径，这个就有点意思了，不会
2016.2.29还是不会
2016.3.2大概懂了，我们在每一次增广的时候，纪录一个to[x]..就是我们所谓的路径覆盖，在结束dinic之后，输出路径覆盖的集合就好了
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int inf=0x7fffffff; 8 struct edge{ 9 int to,cap,next;10 }e[30000]; 11 int h[405],mark[405],to[405];12 int n,m,s,t;13 int last[405],iter[405],ecnt=1;14 void insert(int from,int to,int cap){15 e[++ecnt]=(edge){to,cap,last[from]};last[from]=ecnt;16 e[++ecnt]=(edge){ from,0,last[to]};last[to]=ecnt;17 } 18 bool bfs(int s,int t){19 memset(h,-1,sizeof(h));20 queue q;21 q.push(s);h[s]=0;22 while(!q.empty()){23 int c=q.front();q.pop(); 24 for(int u=last[c];u;u=e[u].next){25 if(e[u].cap>0&&h[e[u].to]==-1){26 h[e[u].to]=h[c]+1;27 q.push(e[u].to);28 }29 }30 }31 return h[t]!=-1;32 }33 int dfs(int x,int t,int f){34 if(x==t) return f;35 int w,used=0;36 for(int u=iter[x];u;u=e[u].next){37 if(h[e[u].to]==h[x]+1){38 w=dfs(e[u].to,t,min(f-used,e[u].cap));39 if(w){40 to[x]=e[u].to;41 if(e[u].to-n>0)42 mark[e[u].to-n]=1;43 }44 e[u].cap-=w;45 e[u^1].cap+=w;46 if(e[u].cap) iter[x]=u;47 used+=w;48 if(used==f) return f; 49 }50 }51 if(!used)h[x]=-1;52 return used;53 }54 int dinic(int s,int t){55 int flow=0;56 while(bfs(s,t)){57 for(int i=0;i<=t;i++) iter[i]=last[i];58 flow+=dfs(s,t,inf);59 }60 return flow; 61 }62 int edge[6005][2];63 int main(){64 scanf("%d %d",&n,&m);65 for(int i=1;i<=m;i++){66 scanf("%d %d",&edge[i][1],&edge[i][2]);67 }68 s=0;t=n+n+1;69 for(int i=1;i<=n;i++){70 insert(s,i,1);71 insert(n+i,t,1);72 }73 74 for(int i=1;i<=m;i++){75 insert(edge[i][1],edge[i][2]+n,1);76 }77 int H=dinic(s,t);78 for(int i=1;i<=n;i++){79 if(mark[i])continue;80 printf("%d",i);81 int k=i;82 while(to[k])83 {84 printf(" %d",to[k]-n);85 k=to[k]-n;86 }87 printf("\n");88 }89 printf("%d",n-H);90 }
04 魔术球问题
3.2 一看就是打表啊