【题目链接】 

 

【题目大意】

　　给出一张无向边权图，每个点最多可以生产b[i]商品，每件代价为a[i],

　　每个点最多可以卖出d[i]商品，收益为c[i]，

　　每个商品在每条边上的运输价值为数量乘长度，求最大纯收益

 

【题解】

　　我们从源点向每个点连价值为-c，流量为d的边

　　由每个点连价值为a，流量为b的边，计算最小费用可行流就是答案。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=2000,M=10000;namespace Min_Cost_Max_Flow{    const int INF=0x3f3f3f3f;    int S,T,cnt,ans,d[N],from[N],g[N],flow;    struct edge{int from,to,nxt,c,v;}e[M];    void add(int u,int v,int w,int c){        e[++cnt].from=u;e[cnt].to=v;        e[cnt].nxt=g[u];g[u]=cnt;        e[cnt].c=c;e[cnt].v=w;    }void add_edge(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);}    bool spfa(){        memset(d,INF,sizeof(d)); d[S]=0;        memset(from,0,sizeof(from));        queue
         
           q; q.push(S);        while(!q.empty()){            int now=q.front(); q.pop();            for(int i=g[now];i;i=e[i].nxt){                if(e[i].v&&d[e[i].to]>d[now]+e[i].c){                    d[e[i].to]=d[now]+e[i].c;                    from[e[i].to]=i;                    q.push(e[i].to);                }            }        }return(d[T]<=0); // 求可行流最小费用，因此当费用增量大于0时不继续增加流量    }    void mcf(){        int x=INF;        for(int i=from[T];i;i=from[e[i].from])x=min(x,e[i].v);flow+=x;        for(int i=from[T];i;i=from[e[i].from]){e[i].v-=x;e[i^1].v+=x;ans+=e[i].c*x;}    }    void Initialize(int n){        memset(g,0,sizeof(g));        memset(e,0,sizeof(e));        ans=flow=0; cnt=1;        S=0,T=n+1;    }    void doit(){while(spfa())mcf();}}int n,m,G[N][N];using namespace Min_Cost_Max_Flow;int main(){    while(~scanf("%d%d",&n,&m)){        Initialize(n);        for(int i=1;i<=n;i++){            int a,b,c,d;            scanf("%d%d%d%d",&a,&b,&c,&d);            add_edge(S,i,d,-c);            add_edge(i,T,b,a);        }memset(G,INF,sizeof(G));        for(int i=1;i<=m;i++){            int x,y,z;            scanf("%d%d%d",&x,&y,&z);            if(z