专栏首页calmoundhust Dating With Girls

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 条评论
登录 后参与评论

相关文章

  • Unique Paths

    问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

    用户1624346
  • Spiral Matrix II

    问题:蛇形矩阵 分析:设置变量dir,0123分别代表方向右下左上 class Solution { public: int num[300][300]...

    用户1624346
  • Rotate Image

    问题:矩阵顺时针旋转90度 class Solution { public: bool dfs(vector<vector<int> > &matrix...

    用户1624346
  • hdu 5249 KPI 权值线段树裸题

    用户2965768
  • Unique Paths

    问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

    用户1624346
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • leetcode-367-Valid Perfect Square

    chenjx85
  • 算24

    解题思路: n个数算24,必有两个数要先算。这两个数算的结果,和剩余n-2个数,就构成了n-1个数求24的问题。枚举先算的两个数,以及这两个数的运算方式。n...

    AI那点小事
  • 敢死队

    这里牵涉一个是否要考虑按照顺序的问题。 如 132 和 123 表示的是一种情况,对于这种情况要进行排除 我的思路是 集中从小到大排序。

    用户4492257
  • HDU 5806

    思路:尺取法!!如果已经统计过的数中有k个数是不小于m的,那么后面再加上任意数,这个区间都符合要求。想通了这一点,这道题便好做了。 一发AC

    用户7727433

扫码关注云+社区

领取腾讯云代金券