2最大流 对于每个外籍i,向他可以配合j的英籍 build(i,j,1)
对于每个外籍i build(s,i,1) 对于每个英籍j build(j,t,1)
2.(SCOI2007修车)同一时刻有N位车主带着他们的爱车来到了汽车维修中心 维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的 现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间 费用流 N辆车，M个工人。 把每个工人拆成N个点 A[i][j]表示第i个工人修倒数第j辆车。 对于每辆车i build(s,i,1,0) 和所有n*m拆点build(i,A[j][k],1,time[i][j]*k) 对于所有的拆点 build(A[j][k],t,1,0); 由于求平均ans=最大流/n 考虑第i个工人，他修第j辆车只对后面要修的车有影响，而前面修过的车已经对当前没有影响了 而这个影响就是后面每个将要修理的车都多等待了time的时间 其他边流量都显然为1，每辆车修一次，每个工人一次只能修理一辆车
3.(scut128)给一个长度100的 正整数序列A 定义它的bx子序列是满足 前一个数是后一个数的一个因子 例如 1 2 6 48 96为 1 2 3 6 48 86 96的一个bx序列 对于A 假设 它的最长bx子序列长度为k 求 最少删掉几个数 使得 它的最长子序列长度小于k T组数据 <=20 n <=100 n个数代表A <=10^9 2 4 1 3 2 6//ans=1 6 2 4 8 3 9 27//ans=2 第一组 bx有 1 3 6 和 1 2 6 删掉 1 或 6都可以满足 第二组 bx有 2 4 8 和 3 9 27 任意从两序列各删掉一个才能满足 sol:先dp求出最长的序列 f[i]表示以a[i]结尾的最长bx序列 f[i]=max(f[j]+1) (a[i]%a[j]==0 j<=i)找到k 对于每个点拆点成一进一出两个点 对于所有f[i]==1的点 build(s,i,1); 表示源点连向起点 对于所有f[i]==k的点 build(i+n,t,1); 表示终点连向汇点 对于所有的f[i]==f[j]+1 && a[i]%a[j]==0 && i>=j 的点 build(j+n,i,1) j的出边连向i的进边 这样建图相当于把所有的最长bx子序列全部建了出来 那我们要求的就是 删掉最少的边 让这个网络流中断 相当于每一条连向汇点的边都会在路径上被破坏 这就是求这个图的 最小割 而又有 最大流最小割定理:网络流中,能够从源点到达汇点的最大流量==如果从网络中移除就能够导致网络流中断的边的集合的最小容量和 所以再跑一次最大流即为答案
