poj 3160

2014-11-23 23:33:56 · 作者: · 浏览: 13

粗心了点,就一个强连通缩点,忘了出栈后要标记,找了一天的bug,,,

题意有点难懂,飞鼠想给大家发礼物,收到礼物后大家给飞鼠的满足程度都已数量化。每个人都住一个房间,房间之间的路是单向的,飞鼠可以选任一个点为起点,路可以重复走,房间不能重复访问,但可以经过而不访问。现在问飞鼠得到的满足程度最大会是多少?,有负值,,如果图不形成环,直接求就可以,看了样例可能形成环,所以用Tarjan缩点,,,

#include
#include
#include
#include
#define N 30010
using namespace std;
struct edage
{
	int ed;
	struct edage *next;
}*E[N],*e[N];
struct op
{
	int x,w;
	friend bool operator < (op a, op b)   
    {  
        return a.wed=y;
	q->next=p[x];
	p[x]=q;
}
int n,m,ins[N],belong[N],low[N],dfs[N],cont[N],a[N],idx,ans,inq[N],vis[N],dis[N],dp[N];
stackQ;
void Tarjan(int x)
{
	int v;
	low[x]=dfs[x]=idx++;
	Q.push(x);
	ins[x]=1;
	for(edage *p=E[x];p;p=p->next)
	{
		if(dfs[p->ed]==-1)
		{
			Tarjan(p->ed);
			low[x]=low[x]>low[p->ed] low[p->ed]:low[x];
		}
		else if(ins[p->ed]==1)
			low[x]=low[x]>dfs[p->ed] dfs[p->ed]:low[x];
	}
	if(dfs[x]==low[x])
	{
		
		while(1)
		{
			v=Q.top();
			Q.pop();
			belong[v]=ans;
			ins[v]=0;//就少了这行,找了一天的bug
			if(a[v]>0)
			cont[ans]+=a[v];
			if(v==x)break;
		}
		ans++;	
	}
}
int bfs(int u)
{
	int max=-1;
	priority_queueQQ;
	cur.x=u;
	cur.w=cont[u];
	QQ.push(cur);
	while(!QQ.empty())
	{
		cur=QQ.top();
		QQ.pop();
		if(vis[cur.x]==1)continue;
		if(maxnext)
		{
			if(vis[p->ed]==0)
			{
				next.x=p->ed;
				next.w=cur.w+cont[p->ed];
				QQ.push(next);
			}
		}
	}
	return max;
}
/*int spfa(int s)
{
    int i;
    for(i=1;i<=ans;i++)
    {
        dis[i]=0;
    }
	dis[s]=cont[s];
    queueq;
    q.push(s);
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        for(edage *p=e[w];p;p=p->next)
        {
            if(dis[p->ed]ed])
            {
                q.push(p->ed);
                dis[p->ed]=dis[w]+cont[p->ed];
            }
        }
    }
    int max=-1;
    for(i=1;i<=ans;i++)
    {
        if(maxnext)
			{
				if(belong[i]!=belong[p->ed])
				{
					inq[belong[p->ed]]++;
					addedage(belong[i],belong[p->ed],e);
				}
			}
		}
		int max=-1;
		for(i=0;i