时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB
-
6 6 2 4 3 5 4 4 1 2 2 4 1 3 3 5 3 6 6 3 样例输出 -
13
描述
暑假到了!!小Hi和小Ho为了体验生活，来到了住在大草原的约翰家。今天一大早，约翰因为有事要出去，就拜托小Hi和小Ho忙帮放牧。
约翰家一共有N个草场，每个草场有容量为W[i]的牧草，N个草场之间有M条单向的路径。
小Hi和小Ho需要将牛羊群赶到草场上，当他们吃完一个草场牧草后，继续前往其他草场。当没有可以到达的草场或是能够到达的草场都已经被吃光了之后，小hi和小Ho就把牛羊群赶回家。
一开始小Hi和小Ho在1号草场，在回家之前，牛羊群最多能吃掉多少牧草？
举个例子：
图中每个点表示一个草场，上部分数字表示编号，下部分表示草场的牧草数量w。
在1吃完草之后，小Hi和小Ho可以选择把牛羊群赶到2或者3，假设小Hi和小Ho把牛羊群赶到2：
吃完草场2之后，只能到草场4，当4吃完后没有可以到达的草场，所以小Hi和小Ho就把牛羊群赶回家。
若选择从1到3，则可以到达5，6：
选择5的话，吃完之后只能直接回家。若选择6，还可以再通过6回到3，再到5。
所以该图可以选择的路线有3条：
1->2->4 total: 11
1->3->5 total: 9
1->3->6->3->5: total: 13
所以最多能够吃到的牧草数量为13。
本题改编自USACO月赛金组
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2行：N个正整数，第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000
第3..M+2行：2个正整数，u,v。表示存在一条从u到v的单向路径。1≤u,v≤N
输出
第1行：1个整数，最多能够吃到的牧草数量。
样例输入
提示：强连通分量
小Ho：我觉得这次最大的问题就是会出现环了。
小Hi：假如没有环呢？
小Ho：那样我就可以这么来做：
因为不存在环，那么图就满足了有向无环的性质。我可以利用上次我们解决病毒问题时同样的思路，将累加改为求最大值，利用拓扑排序计算出从起点到当前节点能够得到的最大牧草数量。即：
假设gress[i]表示从起点到草场i累计可以吃到的牧草数量。
grass[i] = max{ grass[j] | j 是 i的前驱结点 } + w[i] 最后我只需要知道最大的grass[i]，就是我们所要寻求的答案。
小Hi：小Ho很厉害嘛，这么快就学会了使用拓扑排序。
小Ho：哎嘿嘿....
小Hi：你说的没错，但是这次的问题最大的限制就是有环的存在。
小Ho：所以有什么办法能够处理么？
小Hi：当然有了，不过首先我们要理解一个新的知识——强连通分量，其定义为：
对于有向图上的2个点a,b，若存在一条从a到b的路径，也存在一条从b到a的路径，那么称a,b是强连通的。
对于有向图上的一个子图，若子图内任意点对(a,b)都满足强连通，则称该子图为强连通子图。
非强连通图有向图的极大强连通子图，称为强连通分量。
特别地，和任何一个点都不强连通的单个点也是一个强连通分量。
对于一个强连通的分量，也就是在其中任意一个点都可以到达其他点。如果草场满足这个性质呢？
小Ho：如果草场是一个强连通图，那么我们只要走到任意一点，就可以把其他所有的草场都走一遍，并且可以选择任意一个点作为终点。
小Hi：没错，再回头看看我们的例子：
同时存在边(3,6)和(6,3)，所以3和6这两个节点也就构成了一个强连通分量。在我们路径中也就存在了3->6->3这样一段。如果换个方式讲的话：
首先到了3，在这个强连通分量中，我们将该分量中所有的点都走过了之后，又重新回到了3。
在处理的时候，我们不妨可以将6和3缩成一个点，那么就可以得到：
这样是不是就变成了你可以解决的问题了？
小Ho：是的，而且答案也没有变化。也就是说我需要满足强连通的点都缩在一起就好了，但是我怎么确定应该缩到哪一点呢？
小Hi：因为一个强连通块会被缩成一个点，那么我们可以直接建立一个新的图，这个图中的点对应的是每一个强连通块。若原图中存在边(u,v)，连接了属于强连通分量A的点u和属于强连通分量B的点v，那么我们就在新图中建立一条边(A,B)。
小Ho：哦，我大概明白了。这次的问题处理方法就是先根据原图找到所有的强连通分量，然后再根据原图边的关系建立新的图，之后再用拓扑排序来处理就可以得到最终结果。
小Hi：没错，就是这样。
小Ho：那么我还有最后一个问题：我们要如何求强连通分量。
小Hi：当然，我们还是得用Tarjan算法来完成了，其伪代码如下：
tarjan(u)
{
Dfn[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
Stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v])
else if (v in Stack) // 如果节点v还在栈内(很重要,无向图没有这一步)
Low[u] = min(Low[u], Dfn[v])
if (Dfn[u] == Low[u]) // 如果节点u是强连通分量的根
repeat
v = Stack.pop // 将v退栈，为该强连通分量中一个顶点
mark v // 标记v，同样通过栈来找连通分量
until (u == v)
}
小Ho：我懂了。我这就去实现它！
小Hi：当然，别忘了还有最重要的一个条件，我们开始在草场1，所以可能有些草场我们是无法到达的，那样的草场需要特殊处理，简单的做法就是将草量处理为0。
小Ho：好，我知道了！
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 20100
#define maxe 200100
struct node
{
int v;
int next;
}Edge[maxe],Edge2[maxe];
int dfn[maxn],low[maxn],stack[maxn],head[maxe],head2[maxe],w[maxn],belong[maxn],n,m,cnt,Index,top,cnt2;
int inDeg[maxn]; //各节点的入度
long long ans,num[maxn],ans2[maxn];
bool instack[maxn],vis[maxn][maxn],vis2[maxn];
set<int>Set;
void AddEdge(int a,int b,node *Edge,int *head)
{
Edge[cnt].v=b;
Edge[cnt].next=head[a];
head[a]=cnt++;
}
void topoSort();
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++Index; // 为节点u设定次序编号和Low初值
stack[++top]=u; // 将节点u压入栈中
instack[u]=true;
for (int i=head[u]; i!=-1; i=Edge[i].next) // 枚举每一条边
{
v=Edge[i].v;
if(!dfn[v]) // 如果节点v未被访问过
{
tarjan(v); // 继续向下找
low[u]=min(low[u],low[v]);
}
else if(instack[v]) // 如果节点v还在栈内(很重要,无向图没有这一步)
{
low[u]=min(low[u],dfn[v]);
}
}
if (dfn[u]==low[u]) // 如果节点u是强连通分量的根
{
cnt2++;
int j;
do
{
j=stack[top--]; // 将v退栈，为该强连通分量中一个顶点
belong[j]=cnt2; //结点j属于新结点cnt2
instack[j]=false; //重置状态
}while (j!=u);
}
}
void dfs(int u, long long w)
{
if(ans<w)
{
ans=w;
}
for (int i=head2[u]; i!=-1; i=Edge2[i].next)
{
dfs(Edge2[i].v, w+num[Edge2[i].v]);
}
}
void ReBuild()
{
int v;
cnt=0;
for (int i=1; i<=n; i++)
{
num[belong[i]]+=w[i]; //更新缩点草的数量
if(vis2[i])
{
Set.insert(belong[i]); //将新结点存入集合中，后面会用
}
}
//重新建图
for (int u=1; u<=n; u++)
{
for (int i=head[u]; i!=-1; i=Edge[i].next)
{
v=Edge[i].v;
if(belong[u]!=belong[v] && !vis[belong[u]][belong[v]])
{
AddEdge(belong[u], belong[v], Edge2, head2);
vis[belong[u]][belong[v]]=1;
inDeg[belong[v]]++;
}
}
}
ans=0;
dfs(belong[1], num[belong[1]]);
printf("%lld\n",ans);
// topoSort(); //使用拓扑排序始终不对
}
void Init() //初始化
{
cnt=0;
Index=0;
top=-1;
memset(head, -1, sizeof(head));
memset(head2, -1, sizeof(head2));
for (int i=0; i<=n; i++)
{
dfn[i]=0;
num[i]=0;
belong[i]=0;
instack[i]=false;
inDeg[i]=0;
ans2[i]=0;
vis2[i]=false;
}
for (int i=0; i<=n; i++)
{
for (int j=0; j<=n; j++)
{
vis[i][j]=0;
}
}
}
//拓扑排序
void topoSort()
{
queue<int>q;
for (set<int>::iterator it=Set.begin(); it!=Set.end(); ++it)
{
ans2[*it]=num[*it];
if(inDeg[*it]==0)
{
q.push(*it);
}
}
int u,v;
while (!q.empty())
{
u=q.front();
q.pop();
for (int i=head2[u]; i!=-1; i=Edge2[i].next)
{
v=Edge2[i].v;
inDeg[v]--;
ans2[v]+=ans2[u];
if (inDeg[v]==0)
{
q.push(v);
}
}
}
long long ans3=0;
for (set<int>::iterator it=Set.begin(); it!=Set.end(); ++it)
{
ans3=max(ans3,ans2[*it]);
}
printf("%lld\n",ans3);
}
void dfs2(int u) //连通性判断
{
vis2[u]=true;
for (int i=head[u]; i!=-1; i=Edge[i].next)
{
if(!vis2[Edge[i].v])
dfs2(Edge[i].v);
}
}
int main()
{
int u,v;
Init();
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
{
scanf("%d",&w[i]);
}
for (int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
AddEdge(u,v,Edge,head);
}
dfs2(1); //检查图的连通性
for (int i=1; i<=n; i++)
{
if (!vis2[i]) //将和结点1没有连通的点的权值置0
{
w[i]=0;
}
}
tarjan(1);
ReBuild();
return 0;
}
使用dfs计算最后结果的是对的，但是用拓扑排序始终不对，这个还待解决。