hust Dating With Girls

#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;
}

#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;
}