首页 > ACM题库 > HDU-杭电 > hdu 2543 飞镖-网络流-[解题报告]C++
2014
02-10

hdu 2543 飞镖-网络流-[解题报告]C++

飞镖

问题描述 :

飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为20个扇形区域,分别标有1到20的分值,每个区域中有单倍、双倍和三倍的区域,打中对应的区域会得到分值乘以倍数所对应的分数。例如打中18分里面的三倍区域,就会得到54分。另外,在镖盘的中央,还有“小红心”和“大红心”,分别是25分和50分。
通常的飞镖规则还有一条,那就是在最后一镖的时候,必须以双倍结束战斗,才算获胜。也就是说,当还剩12分的时候,必须打中双倍的6才算赢,而打中单倍的12或者三倍的4则不算。特别的,“大红心”也算双倍(双倍的25)。
在这样的规则下,3镖能解决的最多分数是170分(两个三倍的20,最后用大红心结束)。
类似的,可以把原来的1到20分的分值扩大为1到K分,同时把小红心的分数扩大为M分(大红心是其双倍),现在3镖能解决的最多分数就不一定是170分了。
在本题中,输入给出K和M,同时给出一个分数C,你需要解决的是能否在3镖内(可以不一定用满3镖)解决C分。同样的,最后一镖必须是双倍,包括大红心。

输入:

输入包含多组数据。每组数据是包含3个整数K,M,C(20<=K,M,C<=10^8)的一行,意义如上面所说。K=M=C=0代表输入结束。

输出:

输入包含多组数据。每组数据是包含3个整数K,M,C(20<=K,M,C<=10^8)的一行,意义如上面所说。K=M=C=0代表输入结束。

样例输入:

20 25 170
30 60 360
30 40 360
0 0 0

样例输出:

Yes
Yes
No

提示:
本题输入、输出都非常多,建议使用printf和scanf代替cout和cin。
暴力的算法将很可能会超过时间限制(Time Limit Exceeded)。

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

本题练习最小费用流。

用队列优化的Bellmanford来寻找增广路,每次找最小费用可行流,对于一条边(u,v),我们规定cap[v][u] = 0,cost[v][u] = -cost[u][v].

由于是无向图,加上反向边,再加上我们要拆成两条边来处理本题,边数×8,即每一条边Add八次类型。如果要处理具有平行边和反向边的情况,如本题,不能采用临界矩阵,本题用前向星。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define Maxn 1005
#define Maxm 80005

int uE[Maxm];
int vE[Maxm];
int cap[Maxm];
int flow[Maxm];
int cost[Maxm];
int next[Maxm];

int first[Maxn];
int pre[Maxn];
int dist[Maxn];//最小花费
int inq[Maxn];
int a[Maxn];//残留网络

int e;
int n,m,c,p;

void init()
{
    memset(first,-1,sizeof(first));
    memset(next,-1,sizeof(next));
}
void addEdge(int x,int y,int a,int b)
{
    uE[e] = x,vE[e] = y,cap[e] = a,cost[e] = b;
    next[e] = first[x];
    first[x] = e;
    e++;
}
int BellmanFord_EdmondsKarp(int s,int t)
{
    int f = 0;
    memset(flow,0,sizeof(flow));
    queue<int> q;
    for(;;)
    {
        memset(inq,0,sizeof(inq));
        memset(a,0,sizeof(a));
        memset(dist,0x3f,sizeof(dist));
        q.push(s);
        inq[s] = 1,dist[s] = 0,a[s] = INF,pre[s] = -1;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for(int i=first[u]; i!=-1; i=next[i])
            {
                int v = vE[i];
                if(flow[i]<cap[i] && dist[u] + cost[i]<dist[v])
                {
                    a[v] = a[u] < cap[i] - flow[i] ? a[u] : cap[i] - flow[i];
                    dist[v] = dist[u] + cost[i];
                    pre[v] = i;//注意此时pre[]的意义是某点的前向边
                    if(!inq[v])
                    {
                        inq[v] = 1,q.push(v);
                    }
                }
            }
        }
        if(dist[t] == INF || a[t] == 0) return f;
        //注意此处转换成long long ,防止数据超出范围,得出相反结论
        if((long long)a[t] * dist[t]<=(long long)c)
        {
            for(int i=pre[t];i!=-1;i=pre[uE[i]])
            {
                flow[i] += a[t];
                flow[i^1] -= a[t];
            }
            f += a[t];
            c -= a[t]*dist[t];
        }
        else
        {
            return f + c/dist[t];
        }
    }
    return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int T;

    int x,y,c1,c2;
    int s,t;
    scanf(" %d",&T);
    while(T--)
    {
        init();
        scanf(" %d %d %d %d",&n,&m,&c,&p);
        e = 0,s = n,t = 1;
        addEdge(s,0,INF,p),addEdge(0,s,0,-p);
        for(int i=0; i<m; i++)
        {
            scanf(" %d %d %d %d",&x,&y,&c1,&c2);
            addEdge(x,y,c1,0),addEdge(y,x,0,0),addEdge(x,y,INF,c2),addEdge(y,x,0,-c2);
            addEdge(y,x,c1,0),addEdge(x,y,0,0),addEdge(y,x,INF,c2),addEdge(x,y,0,-c2);
        }
        int ans = BellmanFord_EdmondsKarp(s,t);
        printf("%d\n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/niuox/article/details/8765461