HDU 3315 My Brute(费用流)

HDU 3315 My Brute(费用流)

http://acm.hdu.edu.cn/showproblem.php?pid=3315

题意:

有S1到Sn这n个勇士要和X1到Xn这n个勇士决斗,初始时,Si的决斗对象是Xi. 如果Si赢了Xi,那么你将获得Vi分,否则你将获得-Vi分. Si和Xi对决时,Si有初始生命Hi,初始攻击Ai, Xi有初始生命Pi,初始攻击Bi. 且Si先出手,然后Xi失去Ai生命,之后如果Xi没死,那么Xi出手,Si失去Bi生命. 直到有一方的生命值<=0时,决斗结束.

现在要你重新安排S和X的决斗顺序,使得你能获得的分最多.如果有多个最优解,你要选取那个维持初始决斗顺序最多的解.

分析:

本题之前用的二分图最优匹配做的:

http://blog.csdn.net/u013480600/article/details/38737449

这里用费用流再做一遍,首先我们求出任意Si与Xj决斗时,你能获得的分值Wij. 下面网络流建图:

源点s编号0, S1到Sn编号1到n, X1到Xn编号n+1到2*n, 汇点t编号2*n+1.

源点s到任意Si点有边 (s, i, 1, 0)

任意Xi点到汇点t有边 (i+n, t, 1, 0)

如果Si与Xj决斗的解过为Wij分值,那么有下面两种情况:

i==j时, 有边(i ,j+n, 1, -Wij*(n+1)-1) (注意这里Wij取负数且乘以(n+1)且减一,取负数,是因为最终结果取反是你能获得的最大分数. 减一是使得该原始决斗顺序能够得以保留. 乘以(n+1)是因为把权值扩大n+1倍之后再+1 最终的权值就算是+n了然后除以(n+1)还是能得到正真的分数值 )

i!=j时,有边(i,j+n,1,-Wij*(n+1) )

最终我们求最小费用的负数X即可. X%(n+1)就是我们保持原先决斗顺序的个数,X/(n+1)就是我们能获得的最终分数.

AC代码: G++提交

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn=200+5;//这里写180+5就出错,题目n的范围应该<=100

struct Edge
{
    int from,to,cap,flow,cost;
    Edge(){}
    Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
};

struct MCMF
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];
    int p[maxn];
    int d[maxn];
    int a[maxn];

    void init(int n,int s,int t)
    {
        this->n=n, this->s=s, this->t=t;
        edges.clear();
        for(int i=0;i<n;++i) G[i].clear();
    }

    void AddEdge(int from,int to,int cap,int cost)
    {
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int &flow,int &cost)
    {
        queue<int> Q;
        for(int i=0;i<n;++i) d[i]=INF;
        memset(inq,0,sizeof(inq));
        Q.push(s),inq[s]=true,d[s]=0,a[s]=INF,p[s]=0;

        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=0;i<G[u].size();++i)
            {
                Edge &e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.to]>d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    a[e.to]=min(a[u],e.cap-e.flow);
                    p[e.to]=G[u][i];
                    if(!inq[e.to]){inq[e.to]=true; Q.push(e.to);}
                }
            }
        }
        if(d[t]==INF) return false;
        flow += a[t];
        cost += d[t]*a[t];
        int u=t;
        while(u!=s)
        {
            edges[p[u]].flow +=a[t];
            edges[p[u]^1].flow -=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }

    int solve()
    {
        int flow=0,cost=0;
        while(BellmanFord(flow,cost));
        return cost;
    }
}MM;

int n;
int v[maxn],h[maxn],p[maxn],a[maxn],b[maxn];
int ack(int i,int j)//返回Si与Xj决斗的结果分数
{
    int sum1=h[i],sum2=p[j];
    while(true)
    {
        sum2 -= a[i];
        if(sum2<=0) return v[i];
        sum1 -= b[j];
        if(sum1<=0) return -v[i];
    }
}

int main()
{
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1;i<=n;++i) scanf("%d",&v[i]);
        for(int i=1;i<=n;++i) scanf("%d",&h[i]);
        for(int i=1;i<=n;++i) scanf("%d",&p[i]);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<=n;++i) scanf("%d",&b[i]);

        int src=0,dst=2*n+1;
        MM.init(2*n+2,src,dst);
        for(int i=1;i<=n;++i)
        {
            MM.AddEdge(src,i,1,0);
            MM.AddEdge(i+n,dst,1,0);
        }

        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            int score = -ack(i,j)*(n+1);
            if(i==j) --score;
            MM.AddEdge(i,j+n,1,score);
        }

        int ans = -MM.solve();

        int v1=ans/(n+1);//最大分数
        int v2=ans%(n+1);//用到的老边数
        if(v1<=0) printf("Oh, I lose my dear seaco!\n");
        else printf("%d %.3lf%%\n",v1,100.0*v2/n);
    }
    return 0;
}