1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int N = 210; 10 const int M=1001000; 11 const int INF = 1001001010; 12 struct edge{ 13 int u,v,cap,flow; 14 int next; 15 16 ////// 17 }e[M]; 18 int head[N],num; 19 int cur[N],d[N]; 20 bool vis[N]; 21 int s,t; 22 void _add(int u,int v,int cap){ 23 e[num].u = u;e[num].v = v; 24 e[num].cap = cap;e[num].flow = 0; 25 e[num].next = head[u]; 26 27 ////// 28 head[u] = num++; 29 } 30 31 void add(int u,int v,int cap){ 32 _add(u,v,cap); _add(v,u,0); 33 } 34 35 bool BFS(){ 36 memset(vis,0,sizeof(vis)); 37 queue<int> Q; 38 Q.push(s); 39 d[s] = 0; 40 vis[s]=1; 41 while(!Q.empty()){ 42 int x = Q.front(); Q.pop(); 43 for(int i = head[x]; i != -1;i = e[i].next){ 44 if(!vis[e[i].v] && e[i].cap > e[i].flow ){ 45 vis[e[i].v] = 1; 46 d[e[i].v] = d[x] + 1; 47 Q.push(e[i].v); 48 } 49 } 50 } 51 return vis[t]; 52 } 53 54 int DFS(int x, int a){ 55 if(x == t || a == 0) return a; 56 int flow=0,f; 57 58 for(int &i = cur[x]; i != -1; i = e[i].next){ 59 if(d[x] + 1 == d[e[i].v] && (f = DFS(e[i].v, min(a, e[i].cap - e[i].flow))) > 0){ 60 e[i].flow += f; 61 e[i ^ 1].flow -= f; 62 flow += f; 63 a -= f; 64 if(a == 0)break; 65 } 66 } 67 return flow; 68 } 69 int Dinic(){ 70 int flow = 0; 71 while(BFS()){ 72 memcpy(cur,head,sizeof(head)); 73 flow += DFS(s,INF); 74 } 75 return flow; 76 } 77 void init(int n){ 78 memset(head,-1,sizeof(head)); 79 num=0; 80 }
无源无汇有下界可行流
t -> s 连一条 INF cap。
对于 边 u -> v ,下界 c1 ,上界 c2:
s -> v c1
u -> t c1
u -> v c2-c1
存在可行流的满足条件是 所有附加弧满载
Dinic
京公网安备 11010802041100号