bzoj2788&luogu3530 poi2012 festival

bzoj2788&luogu3530 poi2012 festival

​​ 题目描述

A charity festival is taking place in Byteburg, and you are one of the fundraisers.

Unfortunately you have missed some fun activities, including a steeplechase.

Byteasar, an amateur of puzzles, has promised a big donation if you manage to solve his riddle.

You do not know the results of the steeplechase but Byteasar has provided you with partial information.

Now he is asking you what is the maximum possible (consistent with what he has told you) number of different times attained by the runners (some of them may have tied, i.e., reached the finish at the same time).

Byteasar has told you that every runner’s time is an integer multiple of one second. He has also provided you with relations between some of the runners’ times. Specifically, he has given you some of the pairs of runners (A,B)(A,B)(A,B) for which AAA’s time was exactly one second smaller than BBB’s time, and some of the pairs of runners (C,D)(C,D)(C,D) for which CCC’s time was no larger than DDD’s time.

Write a program that will solve the riddle for you!

给定多组限制，限制分成2类，第一类是ax+1=ay 第二类是ax≤ay，求这些数最多有多少种不同的取值

输入输出格式

输入格式：

The first line of the standard input contains three non-negative integers, nnn, m1m_1m1, m2m_2m2 (2≤n≤6002\le n\le 6002≤n≤600, 1≤m1+m2≤100 0001\le m_1+m_2\le 100\ 0001≤m1+m2≤100 000), separated by single spaces, that denote respectively: the number of runners, the number of revealed pairs of the first type (A,B)(A,B)(A,B),and the number of revealed pairs of the second type (C,D)(C,D)(C,D).

The runners are numbered from 1 to nnn.

In the following m1m_1m1 lines the pairs of runners of the first kind are given, one per line - the iii-th such line holds two integers aia_iai and bib_ibi,ai≠bia_i\ne b_iai≠bi, separated by a single space, that denote that runner aia_iai’s time was exactly one second smaller than bib_ibi’s.

In the next m2m_2m2 lines the pairs of runners of the second kind are given, one per line - the iii-th such line holds two integers cic_ici and did_idi,ci≠dic_i\ne d_ici≠di, separated by a single space, that denote that runner cic_ici’s time was no larger than did_idi’s.

输出格式：

In the first and only line of the standard output your program should print a single integer equal to the maximum possible number of different times attained by the runners consistent with the criteria.

If there is no order of runners satisfying Byteasar’s constraints, the program should output a single line holding the word “NIE” (Polish for no), without the quotation marks.

In tests worth at least 15% of points it additionally holds that n≤10n\le 10n≤10.

输入输出样例

输入样例#1：

4 2 2 1 2 3 4 1 4 3 1 输出样例#1：

3 说明

给定多组限制，限制分成2类，第一类是ax+1=ay 第二类是ax≤ay，求这些数最多有多少种不同的取值

夜深人静写算法：​​建立约束条件 首先floyd排除正权回路的可能性

建图之后会存在强连通分量 强连通之间连接的边肯定是m2的边否则 不符合DAG的定义

所以说我每个分量的答案其实是互不干扰的 那么我答案的最大值就是每个分量里的最大值+1相加（也因为约束条件只有三种0，-1，1所以每个点都会被取到）

在一个强连通块中走出一条路径，就对应着一组可能的解。从第一个点开始标号，经过边权为1就加一，经过边权为-1就减一，经过边权为0就不变，这样我们得到的解一定是合法的，因为我们满足了所有的要求，而且我们已经排除了正权回路，即不会出现任何矛盾。同时我们得到的解一定是这条路径上从小到大标号中最优的，因为标号必定是连续的。同时，所有的解都能够在图上找到一条路径与之对应。 若这条路径的开头或结尾是-1，那么我们去掉这个，答案变优了，称这个操作为一次优化，那么对于一条路径，不断地优化，然后除去开头就是(1,−1) 和结尾为 (−1,1) 的，这样答案要么变优，要么不变。

#include#include#include#include#define N 660using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (S==T) return EOF; } return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int y,next;}data[202000];int num,h[N],b[N],stackf[N],low[N],dfn[N],f[N][N],ans[N],n,m1,m2,ans1,s;inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;}stack q;void tarjan(int x){ dfn[x]=++num;low[x]=num;stackf[x]=true;q.push(x); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],dfn[y]); } if (dfn[x]==low[x]){ s++;int y; do{ y=q-();q.pop();b[y]=s;stackf[y]=false; }while (y!=x); }}int main(){ freopen("bzoj2788.in","r",stdin); n=read();m1=read();m2=read();memset(f,0x3f,sizeof(f)); for (int i=1;i<=m1;++i){ int x=read(),y=read();insert1(x,y);insert1(y,x); f[x][y]=min(f[x][y],1);f[y][x]=min(f[y][x],-1); } for (int i=1;i<=m2;++i){ int x=read(),y=read();insert1(y,x);f[y][x]=min(f[y][x],0); } for (int i=1;i<=n;++i) f[i][i]=0; for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j){ f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } for (int i=1;i<=n;++i) if (f[i][i]<0){printf("NIE");return 0;}num=0; for (int i=1;i<=n;++i)if (!dfn[i]) tarjan(i); for (int i=1;i<=s;++i) ans[i]=1; for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if (i!=j&&b[i]==b[j]) ans[b[i]]=max(ans[b[i]],f[i][j]+1); for (int i=1;i<=s;++i) ans1+=ans[i]; printf("%d",ans1); return 0;}

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