題意：

給出一個有向無環圖(DAG)，我們規定有一些邊是必須走的，當走到一個出度是0的點時，我們可以瞬移到任何一個我們想去的點，自選起點，走遍所有的必須走的邊，使得瞬移次數最少。

思路：

這類題完全沒做過啊，賽后問了過了這道題的同學，才知道這么個東西，具體怎么建圖模板里都告訴了，紅書上就有。

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<queue> #include<stack> #include<set> #include<string> #include<vector>using namespace std; const int maxn = 510, maxm = maxn * maxn; const int inf = 1000000000;class MaxFlow//一個挺快的模板,比一般的MaxFlow快,我也不知道為什么。。。 { private:int next[maxm*2];int num[maxm*2];int a[maxn*2];int row_sum[maxn];int col_sum[maxn];int n , m, K;int d[maxn*2], st[maxn*2], cod[maxn][maxn];int h[maxn*2], vh[maxn*2];bool don[maxm*2],in[maxn*2];int dfs(int, int);bool visit(int, int); public:int T;int r[maxm*2];MaxFlow() {}int Addedge(int, int, int);int Run();bool FindCircle();void Init(int m){memset(a, 0, sizeof(a));tt = 1;T = m;}int tt;~MaxFlow() {} } mf;int MaxFlow::Addedge(int x,int y,int rr) {next[++tt]=a[x];num[tt]=y;r[tt]=rr;a[x]=tt;next[++tt]=a[y];num[tt]=x;r[tt]=0;a[y]=tt;return tt; }int MaxFlow::dfs(int x,int y) {if (x==T) return y;int sig=st[x],minh=T+1;do{if (r[st[x]]){if (h[num[st[x]]]+1==h[x]){int k=dfs(num[st[x]],min(y,r[st[x]]));if (k){r[st[x]]-=k;r[st[x]^1]+=k;return k;}}minh=min(minh,h[num[st[x]]]+1);if (h[0]>T) return 0;}st[x]=next[st[x]];if (st[x]==0) st[x]=a[x];}while (sig!=st[x]);if (vh[h[x]]--==0) h[0]=T+1;vh[h[x]=minh]++;return 0; }int MaxFlow::Run() {for (int i=0; i<=T; i++) h[i]=vh[i]=0;for (int i=0; i<=T; i++) st[i]=a[i];vh[0]=T+1;int ret=0;while (h[0]<=T) ret+=dfs(0,K+1);return ret; }bool MaxFlow::visit(int x,int ed) {if (don[ed])return in[x];don[ed]=true;in[x]=true;for (int p=a[x]; p; p=next[p]){if (r[p] && (ed^p)!=1)if (visit(num[p],p)) return true;}in[x]=false;return false; }bool MaxFlow::FindCircle() {for (int i=0; i<=T; i++) in[i]=false;for (int i=1; i<=tt; i++) don[i]=false;for (int i=2; i<=tt; i++){if (r[i] && !don[i]){in[num[i^1]]=true;if (visit(num[i],i)) return true;in[num[i^1]]=false;}}return false; }int cnt[maxn]; //節點的度int main() {int t;scanf("%d",&t);int cas=1;while(t--){int n, m;scanf("%d%d", &n, &m);int ss = 0, tt = n+3;//源點和匯點int s = n + 2, t = n+1;//附加源點和附加匯點mf.Init(tt);//注意模板的坑,此模板的源點一定是0,不能自己設定,匯點就是ttfor (int i = 1; i <= n; i++){mf.Addedge(s, i, inf);mf.Addedge(i, t, inf);}memset(cnt, 0, sizeof cnt);int sum = 0;while (m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);if (w){sum++;cnt[u]--;cnt[v]++;}mf.Addedge(u, v, inf);}for (int i = 1; i <= n; i++){if (cnt[i] < 0)mf.Addedge(i, tt, -cnt[i]);elsemf.Addedge(ss, i, cnt[i]);}mf.Run();int fuck = mf.Addedge(t, s, sum);mf.Run();printf("Case #%d: %d\n", cas++, sum - mf.r[fuck^1]);//為什么異或1,因為這個模板的返回值返回的是反向邊的流量,所以^1了才是正向邊的流量}return 0; }

總結

以上是生活随笔為你收集整理的hust1342(流量有上下界的最小流)的全部內容，希望文章能夠幫你解決所遇到的問題。

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