相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3876
解题报告
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300 + 9; const int M = 20000 + 100 << 1; const int INF = 1e9; int n,m,vout,T,S,V,cnt[N],head[N],to[M],nxt[M],cost[M],flow[M]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v, int f, int c) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c; } class Minimum_Cost_Flow{ int dis[N],sur[N],inq[N]; queue<int> que; public: inline void MaxFlow(bool SPJ=0) { for (int f=INF,w;SPFA();f=INF) { if (SPJ && dis[T] >= 0) return; for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]); for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f; vout += dis[T] * f; } } private: bool SPFA() { memset(dis,60,sizeof(dis)); que.push(S); dis[S] = 0; while (!que.empty()) { int w = que.front(); que.pop(); inq[w] = 0; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] > dis[w] + cost[i] && flow[i]) { dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i; if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]); } } } return dis[T] < INF; } }MCMF; int main() { n = read(); S = 0; T = N - 1; V = N - 2; for (int i=1,k;i<=n;i++) { k = read(); for (int j=1,p,c;j<=k;j++) { p = read(); c = read(); cnt[i]--; cnt[p]++; vout += c; Add_Edge(i, p, INF, c); } Add_Edge(i, V, INF, 0); } Add_Edge(V, 1, INF, 0); for (int i=1;i<=n;i++) { if (cnt[i] > 0) Add_Edge(S, i, cnt[i], 0); else Add_Edge(i, T, -cnt[i], 0); } MCMF.MaxFlow(); for (int i=head[S];i;i=nxt[i]) if (flow[i]) return 1; S = V; T = 1; MCMF.MaxFlow(1); printf("%d\n",vout); return 0; }
whoah this blog is great i really like reading your posts. Stay up the great paintings! You already know, a lot of individuals are searching round for this information, you can aid them greatly.
It¦s actually a great and helpful piece of information. I am glad that you simply shared this useful info with us. Please stay us informed like this. Thank you for sharing.