Colosseo

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 732    Accepted Submission(s): 147 Problem Description Mr. Chopsticks keeps N monsters, numbered from 1 to N. In order to train them, he holds N * (N - 1) / 2 competitions and asks the monsters to fight with each other. Any two monsters fight in exactly one competition, in which one of them beat the other. If monster A beats monster B, we say A is stronger than B. Note that the “stronger than” relation is not transitive. For example, it is possible that A beats B, B beats C but C beats A. After finishing all the competitions, Mr. Chopsticks divides all the monsters into two teams T1 and T2, containing M and N – M monsters respectively, where each monster is in exactly one team. Mr. Chopsticks considers a team of monsters powerful if there is a way to arrange them in a queue (A1, A2, …, Am) such that monster Ai is stronger than monster Aj for any 1<=i<j<=m. Now Mr. Chopsticks wants to check whether T1 and T2 are both powerful, and if so, he wants to select k monsters from T2 to join T1 such that the selected monsters together with all the monsters in T1 can still form a powerful team and k is as large as possible. Could you help him?   Input The input contains multiple test cases. Each case begins with two integers N and M (2 <= N <= 1000, 1 <= M < N), indicating the number of monsters Mr. Chopsticks keeps and the number of monsters in T1 respectively. The following N lines, each contain N integers, where the jth integer in the ith line is 1 if the ith monster beats the jth monster; otherwise, it is 0. It is guaranteed that the ith integer in the jth line is 0 iff the jth integer in the ith line is 1. The ith integer in the ith line is always 0. The last line of each case contains M distinct integers, each between 1 and N inclusively, representing the monsters in T1. The input is terminated by N = M = 0.   Output For each case, if both T1 and T2 are powerful, output “YES” and the maximum k; otherwise, output “NO”.   Sample Input 3 2 0 1 1 0 0 1 0 0 0 3 1 4 3 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 2 3 4 2 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 2 0 0   Sample Output YES 1 NO YES 1 Hint In the third example, Mr. Chopsticks can let the monster numbered 4 from T2 join into T1 to form a queue (1, 2, 4).   Author SYSU   Source 2016 Multi-University Training Contest 7   Recommend wange2014   |   We have carefully selected several similar problems for you:   5842  5841  5840  5839  5838 题目大意：     有V只怪兽，对于任意两只我们都知道哪只可以打败哪只（可能形成环）。给出一些怪兽，问给出的这些怪兽和剩下的怪兽组成的这两组是否没有环，此外，求最多可以从剩下的怪兽中拿多少只加入前面使其继续不成环。 解题思路：     根据题意，这些怪兽的关系形成了一个竞赛图。     竞赛图在百度上的定义如下（感觉描述很奇怪，但还是看得懂的） 每对顶点之间都有一条边相连的 有向图称为竞赛图。 ^[1]  设D为n阶有向 简单图，若D ^[2]  中基图为n阶 无向完全图，则称D是n阶竞赛图。 每对顶点之间都有一条边相连的 有向图称为竞赛图。 ^[1]  设D为n阶有向 简单图，若D ^[2]  中基图为n阶 无向完全图 ，则称D是n阶竞赛图。     利用竞赛图的性质，这题就可以简化很多。     首先我们对选出的和剩下的怪兽进行拓普排序，如果有环不能拓普排序，那么直接输出"NO"。然后我们用O(n^2)的遍历，暴力查找第二组的每一个怪兽如果插入第一组插入的位置，如果不能插入跳过这个怪兽（由于竞赛图的性质，插入位置只能有一个）。然后我们求这个位置序列的LIS（这里可以相等，由于竞赛图的性质，这样插入不可能存在形成环的情况，至于证明自己画一下图就很明显了）。     出题人说这题不卡常，给了标程三倍的时间。然而这题非常恶心地卡读入(╯°Д°）╯︵ /(.□ . \)。我不用gets读入即使开挂也是TLE，用gets才200ms。。。 AC代码： #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; #define INF 0x3f3f3f3f const int maxv=1000+3; int V,N,A[maxv],B[maxv],c[maxv],t,dp[maxv]; int G[maxv][maxv]; vector<int> pos; //int pos[maxv]; bool a_have[maxv]; bool vis[maxv]; char in[maxv*2]; template<class T>//输入挂 inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0;//EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void out(int x)//输出挂 { if(x>9) out(x/10); putchar(x%10+'0'); } bool dfs(int u,bool flag,int *C) { //cout<<"in u: "<<u<<endl; c[u]=-1;//访问标志 for(int v=0;v<V;++v) if(a_have[v]==flag&&G[u][v]) if(c[v]<0) return false;//存在有向环，失败退出 else if(!c[v]&&!dfs(v,flag,C)) return false; //cout<<"out u: "<<u<<endl; c[u]=1; C[--t]=u; return true; } bool toposort(bool flag,int n,int *C) { t=n; memset(c,0,sizeof c); for(int u=0;u<V;++u) if(a_have[u]==flag&&!c[u]) if(!dfs(u,flag,C)) return false; return true; } int main() { while(~scanf("%d%d",&V,&N)&&(V||N)) { getchar(); for(int i=0;i<V;++i) { gets(in);//卡输入，必须用gets for(int j=0;j<V;++j) G[i][j]=in[j<<1]-'0'; } memset(a_have,0,sizeof a_have); for(int i=0;i<N;++i) { int temp; scan_d(temp); a_have[temp-1]=true;//标记哪些怪物被选出来 } if(!toposort(true,N,A)||!toposort(false,V-N,B))//有环 { puts("NO"); continue; } printf("YES "); pos.clear(); for(int i=0;i<V-N;++i) { bool flag=true,ok=true;; int p=N; for(int j=N-1;j>=0;--j) { if(flag) { if(G[B[i]][A[j]]) p=j-1; else flag=false; } else if(G[B[i]][A[j]])//形成环，跳过 { ok=false; break; } } if(ok) pos.push_back(p);//加入位置序列 } size_t n=pos.size(); fill(dp,dp+n,INF); for(int i=0;i<n;++i)//求LIS *upper_bound(dp,dp+n,pos[i])=pos[i]; out(lower_bound(dp,dp+n,INF)-dp); putchar('\n'); } return 0; }