ADO.NET入门笔记

Father Christmas flymouse
Time Limit: 1000MS   Memory Limit: 131072K
Total Submissions: 2417   Accepted: 804

Description

After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.

During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.

Input

The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms andM direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and jindicating a directed path from the i-th room to the j-th one. Process to end of file.

Output

For each test case, output one line with only the maximized sum of accumulated comfort indices.

Sample Input

2 2
14
21
0 1
1 0

Sample Output

35

Hint

32-bit signed integer type is capable of doing all arithmetic.

Source


飞鼠要给大家发礼物,收到礼物后,都会对飞鼠有一个舒适指数,这个指数可以为正也可以是负。每个人都有一个房间,而且都是单向连接的,飞鼠在送礼物经过他们的房间的时候可以选择不进去,问飞鼠最多能够获得多少舒适指数。
负分的房间肯定不能去访问,因为有环,所以要进行缩点,缩点的过程中只把正分加上,缩完点之后,可能有多个入度为0的点,可以建立一个超级源点,与它们连接,最后就会形成一颗树的形状,然后跑一边spfa,求出源点到每片叶子的最大距离,取其中最大的即为所求。
//1980K	47MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define M 30007
#define inf 0x3f3f3f
using namespace std;
int dfn[M],low[M],belong[M],head[M],stack[M],vis[M];
int num,cnt,scnt,begin;
int n,m,val[M],sum_val[M],dis[M],in[M],out[M],head1[M];
struct E
{
    int v,to;
}edg[M*10];
struct NE
{
    int v,to,w;
}path[M*10];
void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(belong,0,sizeof(belong));
    memset(head,-1,sizeof(head));
    memset(head1,-1,sizeof(head1));
    memset(stack,0,sizeof(stack));
    memset(vis,0,sizeof(vis));
    memset(sum_val,0,sizeof(sum_val));
    memset(val,0,sizeof(val));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    cnt=scnt=num=begin=0;
}
void init_new()
{
    memset(head1,-1,sizeof(head1));
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    num=0;
}
void addedge(int u,int v)
{
    edg[num].v=v;edg[num].to=head[u];
    head[u]=num++;
}
void addedge1(int u,int v,int w)
{
    path[num].v=v;path[num].w=w;
    path[num].to=head1[u];
    head1[u]=num++;
}
void tarjan(int x)
{
    int v;
    dfn[x]=low[x]=++cnt;
    stack[++begin]=x;
    for(int i=head[x];i!=-1;i=edg[i].to)
    {
        v=edg[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(!vis[v])
            low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        scnt++;
        do
        {
            v=stack[begin--];
            belong[v]=scnt;
            vis[v]=1;
        }while(v!=x);
    }
}

int spfa(int s)
{
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head1[u];i!=-1;i=path[i].to)
        {
            int v=path[i].v;
            if(dis[v]<dis[u]+path[i].w)
            {
                dis[v]=dis[u]+path[i].w;
            }
            if(!vis[v])
            {
                q.push(v);
                vis[v]=1;
            }
        }
    }
    int maxx=0;
    for(int i=1;i<=scnt;i++)
        if(!out[i])maxx=max(maxx,dis[i]);
    return maxx;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        int a,b;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addedge(a+1,b+1);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        init_new();
        for(int u=1;u<=n;u++)
           if(val[u]>0)
                sum_val[belong[u]]+=val[u];
        for(int u=1;u<=n;u++)
            for(int i=head[u];i!=-1;i=edg[i].to)
            {
                int v=edg[i].v;
                if(belong[u]!=belong[v])
                {
                    in[belong[v]]++;
                    out[belong[u]]++;
                    addedge1(belong[u],belong[v],sum_val[belong[v]]);
                }
            }
        for(int i=1;i<=scnt;i++)
            if(!in[i])addedge1(0,i,sum_val[i]);
        printf("%d\n",spfa(0));
    }
    return 0;
}


ADO.NET入门笔记,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。