HDU 3667 Transportation （最小費用最大流）

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 
    
    
     題意：有n個城市，m條單向路。現在運送貨物，每條路有一個系數ai有最多能運的貨物數ci，費用關系為val=ai*x*x,(其中x為運送貨物數,x<=ci)，問你把K件貨物從1城市運到n城市最少需要多少費用，如果不能運完輸出-1。
    
    
     分析：都會想到根據所給的邊建圖，關鍵是怎麼解決費用問題，因為費用是個函數關系，這一點其實大白書上有說過如何建圖。我們可以舉個例子看看：假如貨物系數為ai，現在運送的貨物從1件到4件費用分别是：ai*1，ai*4,ai*9,ai*16,兩兩相減得到：ai*1,ai*3,ai*5,ai*7...意思就是運送貨物為x件，就是這個等差數列的前x項和，那麼我們就可以建邊了，假如x城市到y城市路的系數為ai，容量為c，那麼我們可以從x到y建c條容量為1的邊，代表可以走c次，滿足容量問題，而每一條邊的費用依次為ai*1,ai*3,ai*5...，就這樣，跑費用流的時候經過此路第一次就會選費用最小的那條，走第二次時會選擇費用第二大的那條（因為是求最小費用，是以它自動會從小到大選擇，并把結果累加，就實作了這個功能）。
    
    
     
            
#include<cstdio>
#include<string.h>
#include<queue>
#include<algorithm>
#define maxn 1100
#define inf 0x3f3f3f
using namespace std;
struct node
{
    int st;
    int en;
    int flow,cost;
    int next;
}E[maxn*maxn];
int num;
int p[maxn];
void init()
{
    memset(p,-1,sizeof p);
    num=0;
}
void add(int st,int en,int flow,int cost)
{
    E[num].st=st;
    E[num].en=en;
    E[num].flow=flow;
    E[num].cost=cost;
    E[num].next=p[st];
    p[st]=num++;
    E[num].st=en;
    E[num].en=st;
    E[num].flow=0;
    E[num].cost=-cost;
    E[num].next=p[en];
    p[en]=num++;
}
int pre[maxn];
int dis[maxn];
bool fg[maxn];

bool spfa(int st,int en)
{
    for(int i=0;i<=en;i++)
        fg[i]=0,dis[i]=inf,pre[i]=-1;
    queue<int>q;
    q.push(st);
    fg[st]=1;
    dis[st]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        fg[u]=0;
        for(int i=p[u];i+1;i=E[i].next)
        {
            int v=E[i].en;
            if(E[i].flow&&dis[v]>dis[u]+E[i].cost)
            {
                dis[v]=dis[u]+E[i].cost;
                pre[v]=i;
                if(!fg[v])
                {
                    fg[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[en]<inf)
        return 1;
    return 0;
}
int f;
int solve(int st,int en)
{
    int ans=0;
    while(spfa(st,en))
    {
        f++;
        for(int i=pre[en];i+1;i=pre[E[i].st])
        {
            E[i].flow-=1;///每次跑完必為1，因為你的容量都是1
            E[i^1].flow+=1;
            ans+=E[i].cost;
        }
    }
    return ans;
}

int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int x,y,a,c;
            scanf("%d%d%d%d",&x,&y,&a,&c);
            for(int j=1,cnt=1;cnt<=c;j+=2,cnt++) add(x,y,1,a*j);
        }
        add(n,n+1,k,0);///建一個彙點，限制它跑k次
        f=0;
        int ans=solve(1,n+1);
        if(f==k) printf("%d\n",ans);
        else puts("-1");
    }
    return 0;
}