记录编号	177813	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2010] 网络扩容	最终得分	100
用户昵称	真红之蝶	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2015-08-12 19:18:53	内存使用	3.19 MiB

/*先求一遍最大流，解决第一问。
在残量网络中有两类边：
1.剩余流量为零的边将其容量设为无穷，费用设为单位费用。
2.剩余流量不为零的边将其拆为两条边，一条容量设为剩余容量，费用设为0，另一条容量设为无穷，费用设为单位费用。
因为增加k容量，所以新增一个0号点，边（0,1）容量为k，费用为0，同时添加反向边。
最后在新图中跑spfa即可*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,k,a,b,c,d,ans,ask,dis[1005],v[1005],first[1005],deep[1005],tot=1,que[250000],head=0,tail=-1,tat,pre[1005],minn=0x7fffffff;
int minc(int a,int b){return a<b?a:b;}
struct bian
{
    int from,to,ex_fare,flow_fare,next; 
}s[100000];
void add(int a,int b,int c,int d)
{
    s[++tot].from=a;
    s[tot].to=b;
    s[tot].flow_fare=c;
    s[tot].ex_fare=d;
    s[tot].next=first[a];
    first[a]=tot;
    s[++tot].from=b;
    s[tot].to=a;
    s[tot].flow_fare=0;
    s[tot].ex_fare=-d;
    s[tot].next=first[b];
    first[b]=tot;
}
struct data
{
    int q,jvli;
    friend bool operator < (data a,data b)
    {
        return a.jvli>b.jvli;
    }
}cc,cd;
priority_queue<data>q;
int spfa(int x)
{
    memset(dis,63,sizeof(dis));
    memset(v,false,sizeof(v));
    dis[x]=0;
    cc.q=x;
    cc.jvli=0;
    v[x]=1;
    q.push(cc);
    while(!q.empty())
    {
        cd=q.top();
        v[cd.q]=0;
        q.pop();
        for(int i=first[cd.q];i!=-1;i=s[i].next)
        {
            int u=s[i].to;
            if(s[i].flow_fare>0&&dis[u]>dis[cd.q]+s[i].ex_fare)
            {
                dis[u]=dis[cd.q]+s[i].ex_fare;
                pre[u]=i;
                if(!v[u])
                {
                    v[u]=1;
                    cc.q=u;
                    cc.jvli=dis[u];
                    q.push(cc);
                }
            }
        }
    }
    if(dis[n]<100000000)
        return 1;
    else
        return 0;
}
int dfs(int x,int now_fare)
{
    if(x==n)
        return now_fare;
    int rest_fare=0;
    for(int i=first[x];i!=-1;i=s[i].next)
    {
        int j=s[i].to;
        if(s[i].flow_fare>0&&deep[j]==deep[x]+1&&(rest_fare=dfs(j,minc(s[i].flow_fare,now_fare))))
        {
            s[i].flow_fare-=rest_fare;
            s[i^1].flow_fare+=rest_fare;
            return rest_fare;
        }
    }
    return 0;
}
int bfs()
{
    head=0,tail=-1;
    for(int i=1;i<=n;++i) 
        deep[i]=-1;
    deep[1]=1,que[++tail]=1;
    while(head<=tail)
    {
        int u=que[head++];
        for(int i=first[u];i!=-1;i=s[i].next)
        {
            int j=s[i].to;
            if(s[i].flow_fare>0&&deep[j]==-1)
            {
                deep[j]=deep[u]+1;
                que[++tail]=j;
            }
        }
    }
    //printf("%d\n",deep[n]);
    if(deep[n]>0)
        return 1;
    else
        return 0;
}
void dinic()
{
    ans=0;int ts=0;
    while(bfs())
    {
        if(ts=dfs(1,0x7fffffff))
            ans+=ts;
    }
    printf("%d ",ans);
}
void rebuild()
{
    tat=tot;
    s[++tat].from=0;
    s[tat].to=1;
    s[tat].flow_fare=k;
    s[tat].ex_fare=0;
    s[tat].next=first[0];
    first[0]=tat;
    s[++tat].from=1;
    s[tat].to=0;
    s[tat].flow_fare=0;
    s[tat].ex_fare=0;
    s[tat].next=first[1];
    first[1]=tat;
    for(int i=2;i<=tot;++i)
    {
        if((i&1)!=1)
        {
            s[++tat].flow_fare=0x7fffffff;
            s[tat].ex_fare=s[i].ex_fare;
            s[tat].from=s[i].from;
            s[tat].to=s[i].to;
            s[tat].next=first[s[i].from];
            first[s[i].from]=tat;
        }
        else
        {
            s[++tat].flow_fare=0;
            s[tat].ex_fare=-s[i].ex_fare;
            s[tat].from=s[i].from;
            s[tat].to=s[i].to;
            s[tat].next=first[s[i].from];
            first[s[i].from]=tat;
        }
        s[i].ex_fare=0;
    }
}
void min_fareflow()
{
    minn=0x7fffffff;
    for(int i=pre[n];i;i=pre[s[i].from])
        minn=minc(minn,s[i].flow_fare);
    //printf("%d\n",minn);
    for(int i=pre[n];i;i=pre[s[i].from])
    {
        s[i].flow_fare-=minn;
        s[i^1].flow_fare+=minn;
        ask+=minn*s[i].ex_fare;
    }
}
int main()
{
    freopen("networkzj2010.in","r",stdin);
    freopen("networkzj2010.out","w",stdout);
    memset(first,-1,sizeof(first));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    dinic();
    rebuild();
    //for(int i=1;i<=tat;++i)
        //printf("%d %d %d %d %d\n",s[i].from,s[i].to,s[i].next,s[i].flow_fare,s[i].ex_fare);
    while(spfa(0))
        min_fareflow();
    printf("%d",ask);
    getchar();getchar();getchar();getchar();
    return 0;
}