网站内容怎么写有利于排名,wordpress 新浪微博登入,洛阳gjyl设计院,黄聪开发wordpress主题1179: [Apio2009]Atm Description Input 第一行包含两个整数N、M。N表示路口的个数#xff0c;M表示道路条数。接下来M行#xff0c;每行两个整数#xff0c;这两个整数都在1到N之间#xff0c;第i1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行#xff0c… 1179: [Apio2009]Atm Description Input 第一行包含两个整数N、M。N表示路口的个数M表示道路条数。接下来M行每行两个整数这两个整数都在1到N之间第i1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行每行一个整数按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、PS表示市中心的编号也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数表示P个有酒吧的路口的编号 Output 输出一个整数表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。 Sample Input 6 71 22 33 52 44 12 66 510128161 51 44356 Sample Output 47 HINT 50%的输入保证N, M3000。所有的输入保证N, M500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。 分析 这道题其实很迷。首先这道题发现如果在一个强连通分量里面都可以走到而且也没有限制走的次数所以我们可以将在强连通分量里面的点缩成一个全新的点。之后造出来一个全新的图。boom新造出来的图可以走一遍最短路spfa。就好了。 至于怎么缩点。用并查集先找到父亲与儿子。之后每次判断出一个强量通分量就用将他们的父亲全连成第一个数。之后在新建图如果一个点的父亲与儿子的父亲不相同那他们1连上2建边这个边其实可以重复利用。这样可以节省空间。 #includecstdio
#includestring.h
#includealgorithm
using namespace std;
struct node{int infont,v,next,val;
}edge[1000010];
int strack[1000010],cnt,father[1000000],heads[500010],d[500010],s,p;
int DFN[1000000],LOW[1000000],bar[1000000],visit[1000010],du[500010];
int n,m,index_1,head;
void address(int x,int y){edge[cnt].infontx;edge[cnt].vy;edge[cnt].nextheads[x];heads[x]cnt;return ;
}
void tarjan(int x){LOW[x]DFN[x]index_1;visit[x]1;strack[head]x;for(int iheads[x];i!-1;iedge[i].next){if(!DFN[edge[i].v]){tarjan(edge[i].v);LOW[x]min(LOW[x],LOW[edge[i].v]);}else if(visit[edge[i].v]){LOW[x]min(LOW[x],DFN[edge[i].v]);}}if(LOW[x]DFN[x]){while(strack[head]!x){visit[strack[head]]0;d[x]d[strack[head]];father[strack[head]]x;head--;}head--;visit[x]0;}return ;
}
void build(){memset(heads,-1,sizeof(heads));cnt0;for(int i1;im;i){if(father[edge[i].infont]!father[edge[i].v])address(father[edge[i].infont],father[edge[i].v]);}return ;
}
void SPFA(int x)
{memset(visit,0,sizeof(visit));memset(strack,0,sizeof(strack));memset(du,-0x3f,sizeof(du));int last;lasthead1;strack[head]x;visit[x]1;du[x]d[x];while(headlast){int newsstrack[head];for(int iheads[news];i!-1;iedge[i].next){if(du[edge[i].v]du[news]d[edge[i].v]){du[edge[i].v]du[news]d[edge[i].v];if(visit[edge[i].v])continue;visit[edge[i].v]1;strack[last]edge[i].v;}}head;visit[news]0;}return ;
}
int main( ){memset(heads,-1,sizeof(heads));scanf(%d%d,n,m);int a,b;for(int i1;im;i){scanf(%d%d,a,b);address(a,b);}for(int i1;in;i){scanf(%d,a);d[i]a;father[i]i;}for(int i1;in;i)if(!DFN[i])tarjan(i);build();scanf(%d%d,a,b);SPFA(father[a]);int ans0;for(int i1;ib;i){scanf(%d,a);ansmax(ans,du[father[a]]);}printf(%d,ans);return 0;
}转载于:https://www.cnblogs.com/uncle-lu/p/5970686.html
