剑客决斗
来源：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]=;
for(int i=;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]=; }while(u!=v);
}
}
bool vis[N];
void dfs(int x){
vis[x]=;
for(int j=;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=;
memset(low,,sizeof low);
memset(dfn,,sizeof dfn);
memset(sum,,sizeof sum);
memset(vis,,sizeof vis);
memset(id,,sizeof id);
memset(mark,,sizeof mark);
memset(grap,,sizeof grap);
while(!s.empty()) s.pop();
scanf("%d",&n);
for(int i=,x;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&x);
if(x) grap[i].push_back(j);
}
}
for(int i=;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
//if(sd==1) {printf("0\n");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\n",ans==1?sum[p]:0);*/
//if(sd==n){puts("1");continue;}
int ans=;
for(int i=;i<=sd;i++){
if(sum[sd]>) ans+=sum[sd];
}
//再加上最长连操作
if(sd==n&&!ans){
for(int i=;i<=n;i++){
if(!vis[i]){
dfs(i);ans++;
}
}
printf("%d\n",ans);
}
else printf("%d\n",ans);
for(int i=;i<=n;i++) grap[i].clear();
}
return ;
}
题意不清：请看《黑书》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,,sizeof meet);
scanf("%d",&n);
for(int i=;i<n;i++){
for(int j=;j<n;j++){
scanf("%d",&beat[i][j]);
}
}
for(int i=;i<n;i++) meet[i][(i+)%n]=;//初始时候,只能确定相邻的两个人能相遇
for(int i=;i<=n;i++){//中间间隔 i 个人
for(int end,start=;start!=n;start++){
end=(i+start)%n;
if(meet[start][end]) continue;
for(int k=(start+)%n;k!=end;k=(k+)%n){//这里一定要注意，不能写成k<end
if(meet[start][k]&&meet[k][end]&&(beat[start][k]||beat[end][k])){//因为涉及到取余操作,而且最后是判断循环一圈和自己比较
meet[start][end]=;break;
}
}
}
}
int ans=;
for(int i=;i<n;i++) if(meet[i][i]) ans++;
printf("%d\n",ans);
}
return ;
}