/** 题目：度度熊的交易计划 链接：http://acm.hdu.edu.cn/showproblem.php?pid=6118 题意：度度熊参与了喵哈哈村的商业大会，但是这次商业大会遇到了一个难题： 喵哈哈村以及周围的村庄可以看做是一共由n个片区，m条公路组成的地区。 由于生产能力的区别，第i个片区能够花费a[i]元生产1个商品，但是最多生产b[i]个。 同样的，由于每个片区的购买能力的区别，第i个片区也能够以c[i]的价格出售最多d[i]个物品。 由于这些因素，度度熊觉得只有合理的调动物品，才能获得最大的利益。 据测算，每一个商品运输1公里，将会花费1元。 那么喵哈哈村最多能够实现多少盈利呢？ 思路:最小费用最大流。 */ #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <queue> #include <iostream> #include <vector> using namespace std; typedef long long LL; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; const int maxn = 5e2+100; int a[maxn], b[maxn], c[maxn], d[maxn]; int f[maxn][maxn]; int n, m; struct Edge { int from, to, cap, flow, cost; }; struct MCMF { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n = n; for(int i = 0; i < n; i++){ G[i].clear(); } edges.clear(); } void AddEdge(int from,int to,int cap,int cost) { edges.push_back((Edge){from,to,cap,0,cost}); edges.push_back((Edge){to,from,0,0,-cost}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s,int t,int &flow,int &cost){ for(int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < (int)G[u].size(); i++){ Edge&e = edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){ d[e.to] = d[u]+e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u],e.cap-e.flow); if(!inq[e.to]) {Q.push(e.to); inq[e.to] = 1;} } } } if(d[t] >= 0) return false;///由于求最大费用. flow += a[t]; cost += d[t]*a[t]; int u = t; while(u!=s){ edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } int Mincost(int s,int t) { int flow = 0, cost = 0; while(BellmanFord(s,t,flow,cost)){ } return cost; } }; struct edge{int to, cost;}; typedef pair<int,int> P; int V; vector<edge> G[maxn]; int dis[maxn][maxn]; void dijkstra(int s) { priority_queue<P, vector<P>, greater<P> > que;///按照first，小的先出。 fill(dis[s],dis[s]+V,INF); dis[s][s] = 0; que.push(P(0,s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(dis[s][v]<p.first) continue; for(int i = 0; i < (int)G[v].size(); i++){ edge e = G[v][i]; if(dis[s][e.to]>dis[s][v]+e.cost){ dis[s][e.to] = dis[s][v]+e.cost; que.push(P(dis[s][e.to],e.to)); } } } } void floyd() { for(int k = 0; k < n; k++){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ f[i][j] = min(f[i][j],f[i][k]+f[k][j]); } } } } int main() { MCMF mcmf; while(scanf("%d%d",&n,&m)==2) { int s = n, t = n+1; mcmf.init(t+2); for(int i = 0; i<n; i++){ scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); mcmf.AddEdge(s,i,b[i],a[i]);///求最大费用。 mcmf.AddEdge(i,t,d[i],-c[i]); } int u, v, k; for(int i = 0; i < n; i++) G[i].clear(); for(int i = 0; i < m; i++){ scanf("%d%d%d",&u,&v,&k); if(u==v) continue; u--, v--; G[u].push_back((edge){v,k}); G[v].push_back((edge){u,k}); } V = n; for(int i = 0; i < V; i++){ dijkstra(i); } //floyd();///可改成求n次dijkstra，复杂度为N*lg(E); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i==j) continue; if(dis[i][j]!=INF&&c[j]-dis[i][j]-a[i]>0){ mcmf.AddEdge(i,j,INF,dis[i][j]); } } } printf("%d ",-mcmf.Mincost(s,t)); } return 0; }