剑客决斗
来源：Polish Olympiad in Informatics（波兰信息学奥林匹克竞赛）
时间限制：5000 ms | 内存限制：65535 KB
难度：5
- 描述
-
在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，则最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。
假设现在n个人围成一个圈，按顺序编上编号1~n。一共进行n-1场决斗。第一场，其中一人（设i号）和他右边的人（即i+1号，若i=n，其右边人则为1号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知n个人之间的强弱关系（即任意两个人之间输赢关系）。如果存在一种抽签方式使第k个人可能胜出，则我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。
- 输入
- 第一行是一个整数N(1<=N<=20)表示测试数据的组数。
第二行是一个整数n表示决斗的总人数。(2<=n<=500)
随后的n行是一个n行n列的矩阵，矩阵中的第i行第j列如果为1表示第i个人与第j个人决斗时第i个人会胜出，为0则表示第i个人与第j个人决斗时第i个人会失败。 - 输出
- 对于每组测试数据，输出可能胜出的人数，每组输出占一行
- 样例输入
-
1 3 0 1 0 0 0 1 1 0 0
- 样例输出
-
3
- 来源
- 《世界大学生程序设计竞赛高级教程·第一册》
- 上传者
- 张云聪
WA代码：
//第一次做，只想着暴力判环与找有几条链，可能少考虑情况了 #include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<stack> using namespace std; #define N 10010 vector<int>grap[N]; stack<int>s; int low[N]; int dfn[N]; int mark[N]; int id[N]; int pd; int sd; int sum[N]; void tarjan(int v){ low[v]=dfn[v]=++pd; s.push(v); mark[v]=1; for(int i=0;i<grap[v].size();i++){ int w=grap[v][i]; if(!dfn[w]){ tarjan(w); low[v]=min(low[v],low[w]); } else if(mark[w]){ low[v]=min(low[v],dfn[w]); } } int u; if(low[v]==dfn[v]){ sd++; do{ u=s.top(); s.pop(); id[u]=sd; sum[sd]++; mark[u]=0; }while(u!=v); } } bool vis[N]; void dfs(int x){ vis[x]=1; for(int j=0;j<grap[x].size();j++){ int v=grap[x][j]; if(!vis[v]) dfs(v); } } int main(){ //freopen("sh.txt","r",stdin); int n,T; scanf("%d",&T); while(T--){ pd=sd=0; memset(low,0,sizeof low); memset(dfn,0,sizeof dfn); memset(sum,0,sizeof sum); memset(vis,0,sizeof vis); memset(id,0,sizeof id); memset(mark,0,sizeof mark); memset(grap,0,sizeof grap); while(!s.empty()) s.pop(); scanf("%d",&n); for(int i=1,x;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&x); if(x) grap[i].push_back(j); } } for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } //if(sd==1) {printf("0 ");return 0;}//如果图已经为强连通图,over /*int in[N]={0},out[N]={0}; for(int i=1;i<=n;i++){//求缩点后，各个顶点的出度和入度 for(int j=0;j<grap[i].size();j++){ int k=grap[i][j]; if(id[i]!=id[k]){ in[id[k]]++; out[id[i]]++; } } } int ans=0,p=0; for(int i=1;i<=sd;i++){ if(!out[i]){ ans++;p=i; } } printf("%d ",ans==1?sum[p]:0);*/ //if(sd==n){puts("1");continue;} int ans=0; for(int i=1;i<=sd;i++){ if(sum[sd]>2) ans+=sum[sd]; } //再加上最长连操作 if(sd==n&&!ans){ for(int i=1;i<=n;i++){ if(!vis[i]){ dfs(i);ans++; } } printf("%d ",ans); } else printf("%d ",ans); for(int i=1;i<=n;i++) grap[i].clear(); } return 0; }
题意不清：请看《黑书》P117例题3。
题解：
这个题有些类似于弗洛伊德算法，将环转化为链，通过dp实现，meet[i][j]表示第i个人是否可以与第j个人存在pk机会，当i＝j时，也就是出现了自己是否可以和自己pk，如果为真，则表示此环可以最后只剩下第i个人，所以他没有下一个pk对象，只能和自己pk，否则，说明这个人不能和自己pk，也就是说，不会出现最后只剩下第i个人的情况。
状态转移方程是：meet[i,j] = true（ 存在k∈链{i,j}使得meet[i,k]且meet[k,j]且(beat[i,k]或beat[j,k]) ）
初始值meet[i,i+1] = true，计算顺序依然是沿对角线的顺序。
AC代码：
#include<cstdio> #include<cstring> using namespace std; #define N 501 bool beat[N][N],meet[N][N]; int n,T; int main(){ scanf("%d",&T); while(T--){ memset(meet,0,sizeof meet); scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&beat[i][j]); } } for(int i=0;i<n;i++) meet[i][(i+1)%n]=1;//初始时候,只能确定相邻的两个人能相遇 for(int i=2;i<=n;i++){//中间间隔 i 个人 for(int end,start=0;start!=n;start++){ end=(i+start)%n; if(meet[start][end]) continue; for(int k=(start+1)%n;k!=end;k=(k+1)%n){//这里一定要注意，不能写成k<end if(meet[start][k]&&meet[k][end]&&(beat[start][k]||beat[end][k])){//因为涉及到取余操作,而且最后是判断循环一圈和自己比较 meet[start][end]=1;break; } } } } int ans=0; for(int i=0;i<n;i++) if(meet[i][i]) ans++; printf("%d ",ans); } return 0; }