首先，如果你要AC这个题目，如果照我的思路来说，你必须知道noi 2008 志愿者招聘

在上上篇论文是有滴...

然后才能做这个题目...

首先题目保证了这是个树，也就是说路径s->t是明确的...

流量平衡是这样建立的...

首先：

把边按容量建立不等式...

假如s->t的路径1、2 都经过w1边分别为x[1],x[2]次

则：

x[1]+x[2] >= w1 ;

增加增量量 , p1==x[1]+x[2]+y[1]==w1 ;

其他都这么建...那么就有n-1个等式了。

然后要新增一个等式，也就增加题目里1->n+1这条边，也就是增加一个这样的等式

pn == 0 ;

然后就是用父亲所在的边减去儿子所在的边。。。//这里是重点啊...

 为什么呢，我们知道啊，流量平衡每一个流只出一次，进一次，就是就说减过后的等式

中，有一个是 -x1 , 一定有一个是 +x1 。这样就保证了流量平衡了

建边就非常简单了

上式减后：0==w1-w1[son] - x[1] -x[2] + x[---] + y[--] - y[1];

这样负号的就连出边去。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define sz 200
#define inf 0x7fffffff
int g[sz][sz];
int s[sz],t[sz],v[sz];

struct node{
    int s, t, v, len, nxt;
} e[sz * 40 + 20];
int hd[sz], cnt, pre[sz] , pos[sz], dis[sz], vis[sz];
int sum ;
void insert(int s, int t, int v, int len){
    e[cnt].s = s;e[cnt].t = t;e[cnt].v = v;e[cnt].len = len;
    e[cnt].nxt = hd[s];hd[s] = cnt++;
    e[cnt].s = t;e[cnt].t = s;e[cnt].v = 0;e[cnt].len = -len;
    e[cnt].nxt = hd[t];hd[t] = cnt++;
    //cout<<s<<" "<<t<<" "<<v<<" "<<len<<endl;
}
bool spfa(int s, int t, int n){
    for(int i = 0; i < n; i++){
        dis[i]=inf;
        vis[i]=0;
        pre[i]=-1;
    }
    queue<int>q;
    while(!q.empty())q.pop();
    q.push(s);
    pre[s] = s;
    dis[s] = 0;
    while( !q.empty() ){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = hd[u]; i!=-1; i=e[i].nxt){
            int v = e[i].t;
            if (e[i].v > 0 && dis[u] + e[i].len < dis[v]){
                dis[v] = dis[u] + e[i].len;
                pre[v] = u;
                pos[v] = i;
                if (!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t] != -1 && dis[t] < inf;
}
int mcf(int s, int t, int n){
    int fw = 0, ct = 0;
    while(spfa(s,t,n)){
        int v = inf;
        for(int i = t; i != s; i = pre[i])
            v = min(v, e[pos[i]].v);
        fw += v;
        ct += dis[t] * v;
        for(int i = t; i != s; i = pre[i]){
            e[pos[i]].v -= v;
            e[pos[i] ^ 1].v += v;
        }
    }
    //cout<<fw<<endl;
    if(fw != sum)return -1;
    return ct; // ct是费用
   // return fw; // fw是最大流值
}
struct node1{
    int s,t,v,nxt;
}ne[sz*10];
int nhd[sz],ncnt;
void insert1(int s ,int t,int v){
    ne[ncnt].s=s;
    ne[ncnt].t=t;
    ne[ncnt].v=v;
    ne[ncnt].nxt = nhd[s];
    nhd[s]=ncnt++;
}
int main(){
    int TT;
    scanf("%d",&TT);
    for(int cas=1;cas<=TT;cas++){
        int n;
        scanf("%d",&n);
        memset(pre,-1,sizeof(pre));
        int S=0,T=n+1;
        memset(hd,-1,sizeof(hd));
        cnt = 0;
        memset(g,-1,sizeof(g));
        memset(pre,-1,sizeof(pre));
        memset(nhd,-1,sizeof(nhd));
        ncnt=0;
        for(int i=1;i<n;i++){
             //cin>>s[i]>>t[i]>>v[i];
             scanf("%d%d%d",&s[i],&t[i],&v[i]);
             g[s[i]][t[i]]=i;
             pre[s[i]] = t[i];
             insert1(t[i],s[i],v[i]);//点的儿子
            //节点...
        }
        s[n]=1;
        t[n]=n+1;
        v[n]=0;
        insert1(n+1,1,0);
        g[1][1+n]=n+1;
        pre[1]=n+1;
        //建立不等式 //////////////
        sum=0;
        for(int i=1;i<=n;i++){//对于每条边，去掉儿子，流入增量
            int vv = v[i];
            for(int j=nhd[s[i]];j!=-1;j=ne[j].nxt){
                vv -= ne[j].v;
                //对于，添加增量，等式左边-y[son]， 流出
                insert(i,g[ne[j].t][s[i]],inf,0);
            }
            if(vv>0){
                sum+=vv;
                insert(S,i,vv,0);//等式右边
            }
            if(vv<0){
                insert(i,T,-vv,0);//等式右边
            }
        }
        ///////////////////////////
        int m;
        cin>>m;
        int ss,tt,li,ci;
        for(int i=0;i<m;i++){
            //cin>>ss>>tt>>li>>ci;
            //对于ss
            scanf("%d%d%d%d",&ss,&tt,&li,&ci);
            insert(g[ss][pre[ss]],g[tt][pre[tt]],li,ci);
        }
        printf("Case #%d: ",cas);
        cout<<mcf(S,T,T+1)<<endl;
    }
}