首页 > ACM题库 > HDU-杭电 > hdu 2452 Navy maneuvers-记忆化搜索-[解题报告]C++
2014
01-26

hdu 2452 Navy maneuvers-记忆化搜索-[解题报告]C++

Navy maneuvers

问题描述 :

In times of peace, various countries have held regular maneuvers to maintain military’s vigilance. There is a navy fleet in a certain country which also starts a new round imaginary naval battle.At the maneuver stage, the admiral intends to assess the combat effectiveness of two warships, “Victory” and “Glory”, so he lets two warships carry out countering exercises. Both of the warship commanders are young and promising, who graduated from naval academy as outstanding students. Not only have they had rich navigation direction experiences, but also have profound scientific knowledge, especially in mathematics.

The admiral appoints one marine area dotted with many islets. Suppose all these islets are occupied by the enemy, and there are positive integers of enemy firebases. The hypothetical exercise situations given by the admiral and the rule of the competition are as follows:

(1) All the occupied islets are connected. There are some routes among these islets, but the route from one islet to another islet is unidirectional. In other words, if we take an islet as a node and an islet route as an edge, then we will get a directed non-cyclic connected graph.
(2) There is a unique 1st islet in the graph. If we start from this islet, we can reach any other islet. (maybe the 1st islet is not the islet which is numbered 1)
(3) At the beginning of the maneuver, two warships simultaneously sail to the 1st islets and eliminate all enemy firebases together.
(4) The two warships, “Victory” and “Glory” take turns to navigate and exchange as soon as they arrive at an islet, then they move forward together. But each time they can only go along the unidirectional route, sail to the islet directly connected to the current, and eliminates all the enemy firebases on the islet. By the way, when start from 1st islet, “Victory” first navigates.
(5) Because each route is unidirectional, and graph is non-cycle, therefore the maneuver terminates when the two warships fail to go on navigating.
(6)When the maneuver ends, sum the numbers of eliminated enemy firebases on the routing path. If the number is greater than or equal to certain number f assigned by the admiral, then “Victory” wins. Otherwise, “Glory” wins.

The warship commanders are both mathematicians. After being assigned to such task, they see it is a Graph Theory problem. On the first simple directed non-cyclic connected graph, each node has a certain positive integer,it indicates the enemy firebases. The assignment is that two captains take turn to move forward along the directed edge until they are unable to do so. Then sum the total positive integers of the nodes on the routing path. Compare the number with the certain number f, and decides the final winning or losses.

Therefore, when it is the time for their own navigation, they are supposed to choose the route to win the final success.

输入:

There are several test cases, in each case there are three positive integers n, m and f in first line. n indicates there are n (1< n <10000 ) nodes in the graph. The node serial number is arranged from 1 to n. m indicates that there are m edges in the graph. The following line has n positive integers, which indicate in sequence the positive integers in the nodes. Finally, there are m lines, and each line has two positive integers a, b (1< = a, b< =n), indicating there is a directed edge from the a node to the b node. Input is terminated by the end of file.

输出:

There are several test cases, in each case there are three positive integers n, m and f in first line. n indicates there are n (1< n <10000 ) nodes in the graph. The node serial number is arranged from 1 to n. m indicates that there are m edges in the graph. The following line has n positive integers, which indicate in sequence the positive integers in the nodes. Finally, there are m lines, and each line has two positive integers a, b (1< = a, b< =n), indicating there is a directed edge from the a node to the b node. Input is terminated by the end of file.

样例输入:

4 4 7
2 2 2 2
4 2
2 1
4 3
3 1
4 5 6
1 2 3 4
1 2
1 3
1 4
2 3
4 3

样例输出:

Glory
Victory

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int N=10009;
const int INF =  0x7fffffff;
int v[N][2];
int wh[N];
struct lin
{
    int nex,to;
} link[N*100];
int first[N];
int n,m,f,cnt;
void add(int f,int t)
{
    link[cnt].to=t;
    link[cnt].nex=first[f];
    first[f]=cnt;
    cnt++;
}
int in[N];
void init()
{
    cnt=0;
    int f,t;
    memset(first,-1,sizeof(first));
    memset(in,0,sizeof(in));
    memset(v,0,sizeof(v));
    for(int i=1; i<=n; i++)
        scanf("%d",&wh[i]);
    for(int i=0; i<m;i++)
    {
        scanf("%d%d",&f,&t);
        in[t]++;
        add(f,t);
    }
}
bool ok;
int dfs(int k,int c)
{
    if(c==1)
    {
        if(v[k][1]) return v[k][1];
        for(int i=first[k];i!=-1;i=link[i].nex)
        {
            int tmp=dfs(link[i].to,0);
            if(tmp>v[k][1])
            v[k][1]=tmp;
        }
        v[k][1]+=wh[k];
        return v[k][1];
    }
    else
    {
        if(v[k][0]) return v[k][0];
        v[k][0]=INF;
        for(int i=first[k];i!=-1;i=link[i].nex)
        {
            int tmp=dfs(link[i].to,1);
            if(tmp<v[k][0])
            v[k][0]=tmp;
        }
        if(v[k][0]==INF)
        v[k][0]=wh[k];
        else
        v[k][0]+=wh[k];
        return v[k][0];
    }
}
void solve()
{
    ok=false;
    for(int i=1;i<=n;i++)
    if(in[i]==0)
    {
        if(dfs(i,1)>=f)
        ok=true;
        if(ok) break;
    }
    if(ok)
    {
        printf("Victory\n");
    }
    else
    {
        printf("Glory\n");
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d%d",&n,&m,&f))
    {
        init();
        solve();
    }
    return 0;
}

解题转自:http://blog.sina.com.cn/s/blog_7be574ed010121dv.html


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?