得到的最小割得到sum?

sum/E 為 最小割

sum%E 為最小割的邊數

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> typedef long long LL; const int MAXN = 10999;//點數的最大值 const int MAXM = 1000010;//邊數的最大值 const LL INF = 1152921504606846976; cost int E = 100001; struct Edge {int to,next;LL cap,flow; }edge[MAXM<<1];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init() {tol = 0;memset(head,-1,sizeof (head)); } void addedge (int u,int v,LL w,LL rw) {edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;edge[tol].next = head[u]; head[u] = tol++;edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;edge[tol].next = head[v]; head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) {memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0] = 1;int front = 0, rear = 0;dep[end] = 0;Q[rear++] = end;while(front != rear){int u = Q[front++];for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i]. to;if(dep[v] != -1)continue;Q[rear++] = v;dep[v] = dep[u] + 1;gap[dep[v]]++;}} } LL S[MAXN]; LL sap(int start,int end, int N) {BFS(start,end);memcpy(cur,head,sizeof(head));int top = 0;int u = start;LL ans = 0;int i;while(dep[start] < N){if(u == end){LL Min = INF;int inser;for( i = 0;i < top;i++){if(Min > edge[S[i]].cap - edge[S[i]].flow){Min = edge[S[i]].cap - edge[S[i]].flow;inser = i;}}for( i = 0;i < top;i++){edge[S[i]]. flow += Min;edge[S[i]^1].flow -= Min;}ans += Min;top = inser;u = edge[S[top]^1].to;continue;}bool flag = false;int v;for( i = cur[u]; i != -1; i = edge[i]. next){v = edge[i]. to;if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){flag = true;cur[u] = i;break;}}if(flag){S[top++] = cur[u];u = v;continue;}int Min = N;for( i = head[u]; i != -1; i = edge[i].next){if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){Min = dep[edge[i].to];cur[u] = i;}}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u] = Min + 1;gap[dep[u]]++;if(u != start)u = edge[S[--top]^1].to;}return ans; } int main() {int n,m,t; // freopen("in.txt","r",stdin);scanf("%d",&t);int cas=1;while(t--){init();scanf("%d%d",&n,&m);for(int i=0; i<m; i++){int u,v,d;LL c;scanf("%d%d%I64d%d",&u,&v,&c,&d);if(d==1){addedge(u,v,c*E+1,c*E+1);}elseaddedge(u,v,c*E+1,0);}printf("Case %d: ",cas++);LL sum=sap(0,n-1,n);printf("%I64d\n",xx%E);}return 0; }
??

轉載于:https://www.cnblogs.com/kewowlo/p/4002576.html

總結

以上是生活随笔為你收集整理的【最小割】HDU 3987 Harry Potter and the Forbidden Forest的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。