HOJ 2543 Stone IV

Description

Recently wywcgs is interested in stones very much. In the past contest, wywcgs has a stone transportation problem. In that problem, he finds a kind of very beautiful stone which made in city A. wywcgs wants to buy this stone as many as possible. These stones must be transfered to the city B that wywcgs lives along a path from A to B. There will be some roads which doesn't have enough capacity to transfer all the stones, so wywcgs must spend money to widen them. But wywcgs has only a little money, so he wants to make an optimal plan to buy and transfer them.

In that problem, wywcgs transfers these stones only along a single path. But he realized that it's better to transfer them along multiple paths. That is to say, he can divide these stones into some groups and transfer each of them along a different path respectively. Now he wants to design a new plan to buy and transfer them.

Input

Input contains multiple test cases. The first line is a integer T, the number of test cases. Each case begins with three integers N, M, C, P, with 2 <= N <= 1000, 1 <= M <= 10000, 1 <= C <= 100000000, 1 <= P <= 10000, represents the number of city, the number of road, the maximum money wywcgs can spend, the cost of one stone respectively. Next M lines each denotes a road. A road is represented by four numbers u, v, c1, c2, with 0 <= u, v < N, 0 <= c1 <= 10000, 0 <= c2 <= 10000, means this road connects the city u and v, its capacity is c1 and wywcgs must spend c2 money to widen its capacity by one. Cities are numbered from 0 to N-1. City 0 is always A, and city 1 is always B. Roads are all bidirectional, and there may be two or more roads connecting to the same pair of city.

Output

For each test case, output a line contains a integer which means the maximum number of wywcgs can buy.

Sample Input

4
2 1 1000 1
0 1 0 2
2 1 1000 1
0 1 1 2
3 1 100000000 1
0 2 10000 0
4 4 4 1
0 2 1 1000
2 1 1 1000
0 3 1 0
3 1 1 1
      

Sample Output

333
334
0
3
      

Hint

Sample 3 : there is no path bwtween 0 and 1, so wywcgs cannot get any stones no matter how much money he has.

Sample 4 : wywcgs can buy 3 stones, 1 stone is transfered along the path 0->2->1 with cost 0, and the other 2 stones are along 0->3->1 with cost 1.

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=2543

大意：

在无向图G中，wywcgs要从源点s购买一些石头并运到汇点t。每块石头单价是P元。每条边i有一个初始容量Ci，当容量超过Ci时，每增加一单位容量要额外花费Ei元。wywcgs现在手头只有C元，问他最多能买多少块石头并成功运到目的地。（2 <= N <= 1000, 1 <= M <= 10000, 1 <= C <= 100,000,000, 1 <= P <= 10000, 0 <= Ci, Ei <= 10000）

思路：这个就是每对点建立两条边就可以了，一条边自然是u到v的花费为0，容量为c1，而另外一条边就是u到v花费为c2，流量为无穷大的。

然后不断增广直到钱不够买一块石头就可以了。

注意：说是流量无穷大，但是要根据范围也不能超long long 啊。亲测INF=1e9不错，本来开始设置的1e8，但是wrong answer，哎，应该是最短路那边的问题，因为肯定是不是超long long 的问题，但是计算了一下也不会超才对，可能某些数据会超吧，毕竟不可能出数据十全十美。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int inf=1e9;
const int MAXN=1000+10;
int n,m;
long long c,p;
int cnt,head[MAXN];
struct node
{
    int u,v,f,w,next;
}edge[80000+5];
void init()
{
    cnt=0;
    for(int i=0;i<n;++i)head[i]=-1;
}
void add(int u,int v,int w,int f)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].f=f;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].u=v;
    edge[cnt].v=u;
    edge[cnt].w=-w;
    edge[cnt].f=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

int dis[MAXN],pre[MAXN];
bool vis[MAXN];
bool spfa()
{
    int i;
    for(i=0;i<n;++i)
    {
        dis[i]=inf;
        vis[i]=0;
        pre[i]=-1;
    }
    queue<int>q;
    q.push(0);
    dis[0]=0;
    while(!q.empty())
    {
        int u=q.front();
        vis[u]=0;
        q.pop();
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            int f=edge[i].f;
            if(f>0&&dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[1]==-1)return 0;
    else return 1;
}

int get_maxflow()
{
    int max_flow=0;
    while(spfa())
    {
        long long ans=0;
        int flow=inf;
        int e=pre[1];
        while(e!=-1)
        {
            flow=min(flow,edge[e].f);
            e=pre[edge[e].u];
        }
        e=pre[1];
        while(e!=-1)
        {
            edge[e].f-=flow;
            edge[e^1].f+=flow;
            e=pre[edge[e].u];
        }
        ans+=flow*dis[1];
        if(c>(ans+p*(long long)flow))
        {
            c-=ans+p*flow;
            max_flow+=flow;
        }
        else
        {
            max_flow+=c/(dis[1]+p);
            break;
        }
    }
    return max_flow;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%I64d%I64d",&n,&m,&c,&p);
        int u,v,w,f;
        init();
        while(m--)
        {
            scanf("%d%d%d%d",&u,&v,&f,&w);
            add(u,v,0,f);
            add(v,u,0,f);
            add(u,v,w,inf);
            add(v,u,w,inf);
        }
        printf("%d\n",get_maxflow());
    }
    return 0;
}