首页 > ACM题库 > HDU-杭电 > HDU 3061-Battle-连通性问题-[解题报告]HOJ
2014
03-01

HDU 3061-Battle-连通性问题-[解题报告]HOJ

Battle

问题描述 :

由于小白同学近期习武十分刻苦,很快被晋升为天策军的统帅。而他上任的第一天,就面对了一场极其困难的战斗:
据侦查兵回报,前方共有N座城池,考虑到地势原因,最终得到一个结论:攻占某些城池之前必须攻占另外一些城池。
事实上,可以把地图看做是一张拓扑图,而攻占某个城池,就意味着必须先攻占它的所有前驱结点。
小白还做了一份调查,得到了攻占每个城池会对他的兵力产生多少消耗(当然也可能会得到增长,因为每攻占一个城池,便可以整顿军队,扩充兵力,天策军的兵力十分庞大,如果不考虑收益,他们可以攻取所有的城池)。
现在请你帮小白统帅做一份战斗计划,挑选攻打哪些城市,使得天策军在战斗过后军容最为壮大。

输入:

首先输入一个N 代表有N个城池(1<= n <= 500)
接着输入一个M,代表城池和城池之间的拓扑关系数。
接着输入N个数字 代表从1 到 N 编号城池的战斗消耗(负数代表将要消耗天策军兵力,正数表示天策军可以获得相应的战斗收益)
最后M行 每行2个数字 a,b,代表相应城池的编号。
表示攻占b之后才可以攻占a;

输出:

首先输入一个N 代表有N个城池(1<= n <= 500)
接着输入一个M,代表城池和城池之间的拓扑关系数。
接着输入N个数字 代表从1 到 N 编号城池的战斗消耗(负数代表将要消耗天策军兵力,正数表示天策军可以获得相应的战斗收益)
最后M行 每行2个数字 a,b,代表相应城池的编号。
表示攻占b之后才可以攻占a;

样例输入:

5 5 
8 
-8 
-10 
12 
-10 

1 2 
2 5 
1 4 
3 4 
4 5

样例输出:

2

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3061

题目大意:攻占每个城池有一定的收益(有正有负),且一个城池的占领要依赖另一些城池,求最大收益。

题目思路:经典题目,附出题人的解题报告:这是一个最小割的模型,具体的构图是:从源点连接正权的点,流量上限为该点的权值;从负权点连接汇点,流量上限为该点权值的绝对值;所有具有拓扑关系的点直接,从st连接end一条INF上限的边;求出最大流,最后用所有正权点的和减去最大流(最小割),便是答案。具体请参见07年的集训队论文《最小割模型在信息学竞赛中的应用》。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 550
int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int dis[Max],gap[Max],pre[Max],cur[Max],p[Max];
int n,m,src,dest,eid;
struct node
 {
     int to,next,c;
 }e[2*Max*Max];
void addedge(int u,int v,int c)
{
    e[eid].to=v;
    e[eid].c=c;
    e[eid].next=p[u];
    p[u]=eid++;
}
int  ISAP(int st,int ed,int n)   ///起点,终点,顶点数
{
    memset(dis, 0, sizeof(dis));
    memset(gap, 0, sizeof(gap));  gap[0]=n;
    memcpy(cur, p, sizeof(p));      ///memcpy!
    int  i,flag,v,u=pre[st]=st,maxflow=0,aug=inf; //puts("akk");
    while(dis[st] < n)
    {
        for(flag=0,i=cur[u];i!=-1; i=e[i].next)  /// cur[u]
            if(e[i].c&& dis[u] == dis[e[i].to]+1)
            {
                flag = 1;

                break;
            }
        if(flag)
        {
            if(aug > e[i].c)
                aug = e[i].c;
            v = e[i].to;
            pre[v] = u;
            cur[u] = i;
            u = v;
            if(u == ed)
            {
                for(u=pre[u]; 1;u=pre[u])    ///notice!
                {
                    e[cur[u]].c -= aug;
                    e[cur[u]^1].c += aug;
                    if(u==st) break;
                   // puts("akkk");
                }
                maxflow += aug;
                aug = inf;
            }
        }
        else
        {
            int minx = n;
            for(i=p[u]; i!=-1; i=e[i].next)
                if(e[i].c&& dis[e[i].to]<minx)
                {
                    minx = dis[e[i].to];
                    cur[u] = i;
                }
            if(--gap[dis[u]] == 0)
                break;
            dis[u] = minx+1;
            gap[dis[u]]++;
            u = pre[u];
        }
    }
//   printf("Case %d:\n%d\n",count,maxflow);
    return maxflow;
}
int main()
{
    int i,val,u,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        src=0;
        dest=n+1;
        eid=0;
        memset(p,-1,sizeof(p));
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&val);
            if(val>0)
            {
                addedge(src,i,val);
                addedge(i,src,0);
                sum+=val;
            }
            else if(val<0)
            {
                addedge(i,dest,-val);
                addedge(dest,i,0);
            }
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v,inf);
            addedge(v,u,0);
        }
        printf("%d\n",sum-ISAP(src,dest,dest+1));
    }
}

参考:http://blog.csdn.net/wings_of_liberty/article/details/7981523


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false