上次学习网络流还是大一的下学期，之后就被从图论分出来交给队友了
然而吉林一战，队友在深圳读研而不能来，于是需要自己学习一下，争取在比赛前看完网络流建模汇总和一些总结，升华一下。
同时记录一下自己做过的题目和想法，相互映照，得出结论
POJ1149
时间看来是很老的题，不过还没有见过，一开始想出来的办法是给人流量，让圈互相给max边，但是后来发现不对，因为如果先给圈边的话，人的次序就不会对ans造成影响，对于这类有时间限制的题，可以对一些被时间影响到的点进行“持久化”，第i+1个状态的流量由第i个状态的流量转移而来，虽然点数变成了点数*时间，但是在二分图下很快，而n*m是1e5，很明显的暗示。
采用dinic进行初始学习
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<queue>
using namespace std;
#define pb push_back #define rep(i, a, b) for (int i=a;i<=b;++i) const int N = 100 * 1000 + 100 + 100 + 5 ;
const int M = 100 * 1000 * 5 + 5 ;
const int INF = 999999999 ;
int src , des , e , head[N] , dis[N] ;
int n , m ; struct Edge {
int v,cap,next;
Edge(){}
Edge(int vv,int cc,int ne) {
v=vv;cap=cc;next=ne;
}
} ed[M] ;
void init() {
e = 0 ;
memset(head,-1,sizeof(head)) ;
}
int bfs() {
memset(dis,0,sizeof(dis)) ;
dis[src] = 1 ;
queue<int>q;
q.push(src) ;
while(!q.empty()) {
int x = q.front(); q.pop() ;
for(int i = head[x] ; i != -1 ; i = ed[i].next) {
int v = ed[i].v ;
if(ed[i].cap && dis[v] == 0) {
dis[v] = dis[x] + 1 ;
if(v == des) {
return 1 ;
}
q.push(v) ;
}
}
}
return 0 ;
}
int dfs(int s,int f) {
if(s == des) return f;
int tmp,cost = 0 ;
for(int i = head[s] ; i != -1 ; i = ed[i].next) {
int v = ed[i].v ;
if(ed[i].cap && dis[s] == dis[v] - 1) {
tmp = dfs(v,min(f-cost,ed[i].cap)) ;
if(tmp > 0) {
ed[i].cap -= tmp;
ed[i^1].cap += tmp ;
cost += tmp ;
if (f == cost)
break ;
}
else dis[v] = -1 ;
}
}
return cost ;
}
int Dinic() {
int ans = 0 ;
while(bfs()) {
ans += dfs(src,INF) ;
}
return ans ;
} void add(int u,int v,int cap) {
ed[e] = Edge(v,cap,head[u]) ;
head[u] = e++ ;
ed[e] = Edge(u,0,head[v]) ;
head[v] = e++ ;
} int a[1050] ;
int b[105][1050] ;
int c[105] ;
int main () {
while(scanf("%d%d" , &m,&n) != EOF) {
init();
src = 0 ;
des = m * n + n + n + 1 ;
rep(i,1,m) {
scanf("%d" , &a[i]) ;
} /// src = 0 ;
/// pig 1~m m+1~m*2 ... m*n
/// peo1 m*n + 1~ m*n + n
/// peo2 m*n + n + 1 ~ m*n + n + n
/// des m*n+n*2+1
rep(i,1,n) {
int nu ; scanf("%d" , &b[i][0]) ;
rep(j,1,b[i][0]) {
scanf("%d" , &b[i][j]) ;
}
scanf("%d" , &c[i]) ;
} rep(i,1,m) {
add(src, i, a[i]) ;
} rep(i,1,n-1) {
rep(j,1,m) {
add((i-1)*m+j,(i)*m+j,INF) ;
}
rep(j,1,b[i][0]) {
rep(k,1,b[i][0]) {
// if(j == k) continue ;
int u = (i-1)*m + b[i][j];
int v = (i)*m + b[i][k] ;
add(u,v, INF) ;
}
}
} rep(i,1,n) {
int u = m * n + i ;
int v = m * n + n + i ;
add(u,v, c[i]) ;
} rep(i,1,n) {
int v = m * n + i ;
rep(j,1,b[i][0]) {
int u = (i - 1) * m + b[i][j] ;
add(u,v, INF) ;
}
} rep(i,1,n) {
int u = m * n + n + i ;
int v = des ;
add(u,v, INF) ;
} printf("%d\n" , Dinic()) ;
}
}
感想：千万不能写错板子，dinic其实是这样的，bfs确定可流，dfs来找出最大的那条流量边，多次dfs其实是M*N*M的复杂度 dfs数量*增广时间
poj2391
这个比较老，一眼就能看出是floyd取minDis然后建二分图，不拆点肯定是错的，甚至连时间都限制不了？
一个坑在于，每次二分都需要重新加边，因为每次图的状态都是残余流量，当然因为i+i^1的cap其实就是i，所以也可以直接扫边更新，不过扫边更新后需要更改板子，需要判断的比较多
后来在比赛的前一天晚上看完了网络流建模汇总，比赛不出意料的没有出网络流。。
工作做完了在学校应该会补完这一部分，为了青岛而努力一下，LCT似乎也是很有趣的算法，不过也需要看一下书。
to be continue....
因为备战EC，自己需要负责网络流，所以重新捡起，主要学习最小费用流
POJ3680
很经典的题型，200个区间中选一些，获得她们的权值，这些区间不能将任意一个点覆盖K次以上
思考发现，如果仅仅从区间的角度上来考虑，将区间化点，是无法在MCMF的过程中控制点被覆盖的次数的，总不能给每个点记录当前被覆盖多少次然后check是否连通。。
所以从点的角度思考，假设有一条从最左点依次向右的流(i,i+1),流量为k，那么每个区间其实是将l到r的流量都减一，然后直接从l跨越到r，因为到l的流量也是从0点的K开始不断的衰减，所以直接进行下去就可以，即建一条边(l,r,1,-c)，最后跑0~m的MCMF
int main () {
int TT ; scanf("%d" , &TT) ;
while(TT--){
int n , k ;
scanf("%d%d" , &n,&k) ;
vector<int>ls;
rep(i,1,n) {
scanf("%d%d%d" , &l[i],&r[i],&c[i]) ;
ls.pb(l[i]) ;
ls.pb(r[i]) ;
}
sort(ls.begin(),ls.end());
ls.erase(unique(ls.begin(),ls.end()),ls.end()) ;
rep(i,1,n) {
l[i] = lower_bound(ls.begin(),ls.end(),l[i])-ls.begin()+1;
r[i] = lower_bound(ls.begin(),ls.end(),r[i])-ls.begin()+1;
}
init() ;
int m = ls.size() ;
for(int i = 0 ; i <= m ; i ++ ) {
addEdge(i,i+1,k,0) ;
}
for(int i = 1 ; i <= n ; i ++ ) {
addEdge(l[i],r[i],1,-c[i]) ;
}
int cost,flow;
MCMF(0,m+1,cost,flow);
printf("%d\n" , -cost) ;
}
}
SPOJ371
n(1000)个箱子里有总共n个小球，每次可以移动一个球到相邻箱子中，问多少步可以让每个箱子最多一个球。
建图比较好想，把球当作流量，des可以从每个箱子中回收一个流量，src会给每个箱子a[i]的流量，流量在箱子之间穿梭的cost是1
建图 (src,i,a[i],0) (i,i-1,INF,1)(i,i+1,INF,1)(i,des,1,0)
不过复杂度是玄学的，spfa是nmm的，t还有20组，看起来有1e10，但是由于spfa复杂度很玄，还是过了
int main () {
int TT ; scanf("%d" , &TT) ;
while(TT--){
int n ; scanf("%d" , &n) ;
rep(i,1,n) scanf("%d" , &a[i]) ;
init() ;
rep(i,1,n) {
addEdge(0,i,a[i],0) ;
addEdge(i,n+1,1,0) ;
int le=i-1;
if(le==0)le=n;
addEdge(i,le,INF,1);
le=i+1;
if(le==n+1)le=1;
addEdge(i,le,INF,1);
}
int cost,flow;
MCMF(0,n+1,cost,flow);
printf("%d\n",cost);
}
}