HDU 3667 Transportation

Transportation
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1688    Accepted Submission(s): 665
Problem Description
There are N cities, and M directed roads connecting them. Now you want to transport K units of goods from city 1 to city N. There are many robbers on the road, so you must be very careful. The more goods you carry, the more dangerous it is. To be more specific, for each road i, there is a coefficient a
i. If you want to carry x units of goods along this road, you should pay a
i * x
2 dollars to hire guards to protect your goods. And what’s worse, for each road i, there is an upper bound C
i, which means that you cannot transport more than C
i units of goods along this road. Please note you can only carry integral unit of goods along each road.
You should find out the minimum cost to transport all the goods safely. 
 
 
Input
There are several test cases. The first line of each case contains three integers, N, M and K. (1 <= N <= 100, 1 <= M <= 5000, 0 <= K <= 100). Then M lines followed, each contains four integers (u
i, v
i, a
i, C
i), indicating there is a directed road from city u
i to v
i, whose coefficient is a
i and upper bound is C
i. (1 <= u
i, v
i <= N, 0 < a
i <= 100, C
i <= 5)
 
 
Output
Output one line for each test case, indicating the minimum cost. If it is impossible to transport all the K units of goods, output -1.
 
 
Sample Input
2 1 2 1 2 1 2 2 1 2 1 2 1 1 2 2 2 1 2 1 2 1 2 2 2
 
 
Sample Output
4 -1 3
 
 
Source
2010 Asia Regional Harbin
 
 
Recommend
lcy
 
 
タイトル:
0からn-1でk個の貨物、m個の辺、各辺、u,v,w,c,;  各辺はxユニットの貨物を運ぶ費用が w*x*x,cは最大流量を表し、
最小費用を求める  ,出力-1を全て搬送できない場合.
 
問題:  端を解いて、この問題の直接的な構想を見て費用の流れで、最初は型版を提出して間違いを発見して、私たちは以前しました  費用は  w*f  ,そして今は  w*f*f(このとき最短では正しい答えが見つからない);
だから私たちは  w*f  ,では、最初の輸送を発見したとき
料金はw、2回目にこの道路を取る場合は3 w(つまり流量が2の場合はw+3 w=4 w)、・・・、i回目にこの道路を取る場合は(2*i-1)*w
にある  u  に着く  u  つながる  c  各辺の流量は1、費用  (2*i - 1)*w
 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int VM=110;
const int EM=501000;
const int INF=0x3f3f3f3f;

struct Edge{
    int u,v,nxt;
    int flow,cost;
}edge[EM<<1];

int n,m,k,cnt,head[VM];
int pre[VM],dis[VM],vis[VM];

void addedge(int cu,int cv,int cw,int cc){
    edge[cnt].u=cu;  edge[cnt].v=cv;  edge[cnt].flow=cw;
    edge[cnt].cost=cc;  edge[cnt].nxt=head[cu];  head[cu]=cnt++;

    edge[cnt].u=cv;  edge[cnt].v=cu;  edge[cnt].flow=0;
    edge[cnt].cost=-cc;  edge[cnt].nxt=head[cv];  head[cv]=cnt++;
}

int src,des;

int SPFA(){
    queue<int> q;
    while(!q.empty())
        q.pop();
    for(int i=0;i<=des;i++){
        dis[i]=INF;
        vis[i]=0;
        pre[i]=-1;
    }
    dis[src]=0;
    vis[src]=1;
    q.push(src);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].v;
            if(edge[i].flow>0 && dis[v]>dis[u]+edge[i].cost){
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return pre[des]!=-1;
}

int flow,cost;

void mincost(){
    flow=0,cost=0;
    while(SPFA()){
        int u=des,minf=INF;
        while(u!=src){
            minf=min(minf,edge[pre[u]].flow);
            u=edge[pre[u]].u;
        }
        u=des;
        while(u!=src){
            edge[pre[u]].flow-=minf;
            edge[pre[u]^1].flow+=minf;
            u=edge[pre[u]].u;
        }
        cost+=minf*minf*dis[des];
        flow+=minf;
    }
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d%d",&n,&m,&k)){
        cnt=0;
        memset(head,-1,sizeof(head));
        int u,v,w,c;
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&u,&v,&w,&c);
            for(int j=0;j<c;j++)
                addedge(u,v,1,w*(2*j+1));
        }
        addedge(0,1,k,0);
        src=0;  des=n;
        mincost();
        if(flow<k)
            printf("-1
");
        else
            printf("%d
",cost);
    }
    return 0;
}