bzoj3832 [Poi2014]Rally

bzoj3832 [Poi2014]Rally

​​ Description An annual bicycle rally will soon begin in Byteburg. The bikers of Byteburg are natural long distance cyclists. Local representatives of motorcyclists, long feuding the cyclists, have decided to sabotage the event. There are intersections in Byteburg, connected with one way streets. Strangely enough, there are no cycles in the street network - if one can ride from intersection U to intersection V , then it is definitely impossible to get from V to U. The rally’s route will lead through Byteburg’s streets. The motorcyclists plan to ride their blazing machines in the early morning of the rally day to one intersection and completely block it. The cyclists’ association will then of course determine an alternative route but it could happen that this new route will be relatively short, and the cyclists will thus be unable to exhibit their remarkable endurance. Clearly, this is the motorcyclists’ plan - they intend to block such an intersection that the longest route that does not pass through it is as short as possible. 给定一个N个点M条边的有向无环图，每条边长度都是1。 请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。 Input In the first line of the standard input, there are two integers, N and M(2<=N<=500 000,1<=M<=1 000 000), separated by a single space, that specify the number of intersections and streets in Byteburg. The intersections are numbered from to . The lines that follow describe the street network: in the -th of these lines, there are two integers, Ai, Bi(1<=Ai,Bi<=N,Ai<>Bi), separated by a single space, that signify that there is a one way street from the intersection no. Ai to the one no. Bi. 第一行包含两个正整数N,M(2<=N<=500 000,1<=M<=1 000 000)，表示点数、边数。 接下来M行每行包含两个正整数A[i],B​​​B%5bi%5d”>i​​​，表示A[i]到B[i]有一条边。 Output The first and only line of the standard output should contain two integers separated by a single space. The first of these should be the number of the intersection that the motorcyclists should block, and the second - the maximum number of streets that the cyclists can then ride along in their rally. If there are many solutions, your program can choose one of them arbitrarily. 包含一行两个整数x,y，用一个空格隔开，x为要删去的点，y为删除x后图中的最长路径的长度，如果有多组解请输出任意一组。 Sample Input 6 5 1 3 1 4 3 6 3 4 4 5 Sample Output 1 2 HINT Source 鸣谢Claris提供SPJ及译文 直接求不好求 可以转化一下增设超级源和超级汇 S,T 那么将图转化为了s->t的最长链 怎么做 我如果每次找出整张图的割来那么因为割一定会经过 我只需要保证我这个割没有经过我要删除的这个点就可以了 那么用可以删除的堆维护即可 首先拓扑排序 然后分别求出s->任意点的最长距离 和任意点到t的最长距离 那么每次我可以先把当前枚举的这个点的被连向的边删去 这样就满足了我割边集不存在关于经过s这个点的边了 为什么是边 因为边我可以认为是s->u->v->t

#include#include#include#include#define N 550000#define M 1100000#define rg registerusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ priority_queue q1,q2; inline void push(int x){q1.push(x);} inline void del(int x){q2.push(x);} inline int qm(){while(!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();if (!q1.empty()) return q1.top();else return 0;}}Q;queue q;struct node1{ int y,next;}data[M],data1[M];int num,num1,h[N],h1[N],n,m,in[N],dis1[N],dis2[N];vector topo;int main(){ //freopen("bzoj3832.in","r",stdin); n=read();m=read();topo.reserve(n+10); for (rg int i=1;i<=m;++i){ int x=read(),y=read();++in[y]; data[++num].y=y;data[num].next=h[x];h[x]=num; data1[++num1].y=x;data1[num1].next=h1[y];h1[y]=num1; } for (rg int i=1;i<=n;++i) if (!in[i]) q.push(i); while(!q.empty()){ int x=q.front();q.pop();topo.push_back(x); for (rg int i=h[x];i;i=data[i].next){ int y=data[i].y;--in[y];if (!in[y]) q.push(y); } }// for (int i=1;i<=n;++i) printf("%d ",topo[i-1]);puts(""); for (rg int i=0;iQ.qm()) ans=Q.qm(),id=x; for (rg int i=h[x];i;i=data[i].next){ int y=data[i].y;Q.push(dis1[x]+dis2[y]); }Q.push(dis1[x]); }printf("%d %d",id,ans-1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。