分类存档：默认分类

好久没有更新这个地方了。

这段时间嘛，开学之流，发生了很多事。下面乱序随便记记。

//

首先是CF红了。本来感觉要一辈子红不了了呢。集训带来的收获还是很大的。以前那样懒懒散散地切题…实在是比不上这种形式的集训。也许有一天，TC也能红一把吧。

//

另外我们队经历了6场contest。

>.<踩了1队两次，也是RP成分居多。

我们队，怎么说呢…还是在各种磨合吧。出题效率明显是比不上team1的。首先本身队员的实力上有差距，然后感觉我们3个各自的手速也拼不过team1…再最后是机子还是经常空的。至少像fancy那样先敲模板什么的还是完全没有的。我们合力写同一个程序也比较罕见(尝试过两次，成功了一次…)，基本上coding部分是分离的。感觉我们该多看看别人的程序风格吧。可能我写的指针式邻接表看着比较费力.要么大家以后就统一用vector写邻接表算了…

现在我们队大致分工是数据结构和图论等带比较经典东西的就给我；然后ZYC负责几何和各路蘑菇题；vout切各种数学题、dp、乱搞题，Java只有vout会，所以大数vout也包办了。

我们队练习的时候往往会开很多个坑…于是很容易就出现每个人手上都有可搞题的代码，但是都只能自己debug的情况。这时候机器就会各种不够用…感觉这种状况几乎是个必然吧.好像没什么特别好的方法，找另外的人看也不一定比自己debug快.

//

然后是选课…神马都被刷了- -，大英都被刷了。更坑爹的是推荐课表里就没有英语这种东西….

接着的话是advanced data structure这门课擦着一个名额选上了。=_=，考试不坑爹的话…大概会毫无压力吧。

数学分析和线性代数用力吧。

//

军训各种坑爹啊，0_0。10点钟才回到寝室。然后他让你在明天6:30 am前把2~10篇400字的军训文交上去。这还不算什么，关键是那天根本就还没有开始军训，只是开了个动员会而已…

就这样吧。

看到AClist里面有dzy就知道是网络流 最后还是没想出来 只好找题解了Orz

基础知识

本题题解 其中那个y[i]前面应该是负号 作者打错了

 判无解的时候是不满流 要用流量判 不要用费用判！！！！

膜拜此题Orz

#include

using namespace std;

const int maxn=2000 + 10, maxm=maxn*maxn*2;

 

const int maxl=999999999;

inline int Min(int a,int b){return a

inline int Max(int a,int b){return a>b?a:b;}

struct st

{

         int y,d;

         int ne;

         int bro;

         int f;

} e[maxm];

int ee;

int st[maxn];

int n,m;

void addedge(int x,int y,int d,int f)

{//给顶点x和y间添加一条费用d,流量f的边

         e[ee].y=y;e[ee].d=d;e[ee].ne=st[x];e[ee].f=f;st[x]=ee++;

         e[ee].y=x;e[ee].d=-1*d;e[ee].ne=st[y];e[ee].f=0;st[y]=ee++;

         e[ee-2].bro=ee-1;e[ee-1].bro=ee-2;

}

int d[maxn],p[maxn];

//spfa所用到起点的最短距离(这里距离相当于cost)和路径记录之前的一个节点

int c[maxn];//spfa所用数组:是否在队列中

int que[maxn],head,tail;//spfa专用队列

int flow=0;

int spfa(int sx,int ex,int n)//求sx到ex的一次费用增广

{//如果没有增广路就返回maxl否则返回费用

         int i,j,k;

         for (i=0;i

         memset(c,0,sizeof(c));//初始化都没进

         d[sx]=0;

         que[head=0]=sx;tail=1;

         c[sx]=1;

         while (head!=tail)//spfa开始

         {

                   k=que[head++];head%=maxn;

                   c[k]=0;

                   for (i=st[k];i!=-1;i=e[i].ne) if (e[i].f)

                            if (d[k]+e[i].d

                            {

                                     d[e[i].y]=d[k]+e[i].d;

                                     p[e[i].y]=i;

                                     if (c[e[i].y]==0)

                                     {

                                               c[e[i].y]=1;

                                               if (e[i].d<0){head=(head-1+maxn)%maxn;que[head]=e[i].y;}

                                               else

                                               {que[tail++]=e[i].y;tail%=maxn;}

                                     }

                            }

         }

         if (d[ex]==maxl) return maxl;//如果无法到达终点返回maxl

         k=maxl;

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)       k=Min(k,e[p[i]].f);//计算流

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)//增加反向边

         {

                   e[p[i]].f-=k;

                   e[e[p[i]].bro].f+=k;

         }

         flow+=k;

         return d[ex]*k;//返回费用为流大小*路径长度(cost累加)

}

int w[200],sumw[200];

int fa[200];

int ui[maxn],vi[maxn],li[maxn],ci[maxn];

int toto=0;

void init()

{

         int i,j,k;

         scanf("%d",&n);

 

         for (i=1;i

         {

                   scanf("%d%d",&j,&k);

                   fa[j]=k;

                   scanf("%d",w+j);

         }

 

         memset(st,-1,sizeof(st));

         ee=0;

         toto=0;

         scanf("%d",&m);

         for (i=1;i<=m;i++)

                   scanf("%d%d%d%d",ui+i,vi+i,li+i,ci+i);

 

 

         for (j=1;j<=m;j++)

                   addedge(ui[j],vi[j],ci[j],li[j]);

         for (i=2;i<=n;i++)

                   addedge(fa[i],i,0,maxl);

 

         memset(sumw,0,sizeof(sumw));

         for (i=2;i<=n;i++)

                   sumw[fa[i]]+=w[i];

         w[1]=0;

         for (i=1;i<=n;i++)

                   if (sumw[i]

                   {

                            addedge(0,i,0,w[i]-sumw[i]);

                            toto+=w[i]-sumw[i];

                   }

                   else

                            if (sumw[i]>w[i])

                                     addedge(i,n+1,0,sumw[i]-w[i]);

}

int main()

{

         int cass,cas=0;

         for (scanf("%d",&cass);cass–;)

         {

                   cas++;

                   init();

                   printf("Case #%d: ",cas);

                   int cost=0;

                   flow=0;

                   while (1)

                   {

                            int k=spfa(0,n+1,n+2);

                            if (k

                                     cost+=k;

                            else

                                     break;

                   }

                   if (flow

                            puts("-1");

                   else

                            printf("%dn",cost);

         }

         return 0;

}