hust Dating With Girls

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B

题意:求最大权值和,起点为1,终点为权值最大的那个点(其权值为负,而且在负数里最大),这题同时要求在到达负最大的权值那个点之前不能经过其他负数的点,

          而且没经过一个点,就加上该点的wi,最后一个点也要加上|wi|

分析:刚开始我是搜索,纯搜,毫无疑问超时~~~

         后来实在无法,搜了解题报告发现是记忆化搜索,不过自己敲出来一直wa,纠结了好久后才知道,原来在取可连通路径最大值那里错了

 记忆化搜索

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MN=110;
const int INF=0x7fffffff;
int map[MN][MN];
int num[MN];
int dp[MN];
int n,m;
int MIN;
int ans;
int e;

int DFS(int cur)
{
    if(dp[cur]>=0) return dp[cur];
    if(cur==e) return -MIN;
    if(num[cur]==-INF) return 0;
    int MAX=0;
    for(int i=1; i<=n; i++)
    {
        if(cur==i) continue;
        if(map[cur][i])
        {
            int tmp=DFS(i);
            if(tmp>0) MAX=max(MAX,num[cur]+tmp);
            //这里的tmp>0必须要有,因为当路径不可达的情况下
            //递归所返回的值是0,而num[cur]>0这样必定比MAX=0
            //大,而其i点本身不可达,又哪来的比较
        }
    }
    return dp[cur]=MAX;
}

int main()
{
    int i,j,a,b;
    int flag;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        flag=false;
        memset(map,0,sizeof(map));
        memset(dp,-1,sizeof(dp));
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        MIN=99999;
        num[1]=0;
        for(i=2; i<=n; i++)
        {
            scanf("%d",&num[i]);
            if(num[i]<0)
            {
                flag=true;
                if(MIN>num[i])
                {
                    MIN=num[i];
                    e=i;
                }
            }
        }
        for(i=2;i<=n;i++)
        {//将所有小于最大负数的点赋予无穷,不可达
            if(num[i]<0 && num[i]>MIN) num[i]=-INF;
        }
        ans=DFS(1);
        if(ans==0 || flag==false) printf("What is a fucking day!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

BFS

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>

using namespace std;
const int MN=110;
const int INF=0x7fffffff;
int map[MN][MN];
int num[MN];
int mmax[MN];
int vis[MN];
int n,m;
int MIN;
int e;

int BFS(int e)
{
    int i,j;
    memset(vis,0,sizeof(vis));
    memset(mmax,-1,sizeof(mmax));
    queue<int>Q;
    Q.push(1);
    vis[1]=0;
    mmax[1]=0;
    while(!Q.empty())
    {
        int head=Q.front();
        Q.pop();
        for(i=1; i<=n; i++)
        {
            if(map[head][i])
            {
                if(num[i]>0)//这里加上vis==0是错的
                {//因为vis的作用只是判断点是否进过队列
                    if(mmax[i]<mmax[head]+num[i])
                        mmax[i]=mmax[head]+num[i];
                }
                if(i==e)
                {
                    if(mmax[i]<mmax[head]-num[i])
                        mmax[i]=mmax[head]-num[i];
                }
                if(num[i]>0 && vis[i]==0)
                {
                    Q.push(i);
                    vis[i]=1;
                }
            }
        }
        vis[head]=0;
    }
}

int main()
{
    int i,j,a,b;
    int flag;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        flag=false;
        memset(map,0,sizeof(map));
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        MIN=99999;
        num[1]=0;
        for(i=2; i<=n; i++)
        {
            scanf("%d",&num[i]);
            if(num[i]<0)
            {
                flag=true;
                if(MIN>num[i])
                {
                    MIN=num[i];
                    e=i;
                }
            }
        }
        for(i=2; i<=n; i++)
        {
            //将所有小于最大负数的点赋予无穷,不可达
            if(num[i]<0 && num[i]>MIN) num[i]=-INF;
        }
        BFS(e);
        if(mmax[e]>0) printf("%d\n",mmax[e]);
        else printf("What is a fucking day!\n");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

26830
来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

6110
来自专栏数据结构与算法

洛谷P4093 [HEOI2016/TJOI2016]序列

题目描述 佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现...

32070
来自专栏聊聊技术

原 初学算法-分治法求平面上最近点对(Cl

609150
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

34570
来自专栏腾讯云实验室

TensorFlow API 简介

腾讯云提供了开发者实验室帮助用户学习 TensorFlow - 相关 API,教程内容如下,用户可以点击开发者实验室快速上机完成实验。

82470
来自专栏WD学习记录

牛客网 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

17810
来自专栏应兆康的专栏

100个Numpy练习【4】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

779120
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

11830
来自专栏自学笔记

Data Structure_图图论带权图

交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

8110

扫码关注云+社区

领取腾讯云代金券