前言:看完题目就不明白了:什么是迭代次数??
从 lyd 原著上才搞明白,就是那 m 组关系中,到第几组关系,能够出现那三种情况中的一种!
update:2022.3.9二刷
正文:
这道题就是看这 m 组关系能否确定每个点的位置。
就相当于,给出 m 组关系,每个关系是 A 的成绩高于 B 的成绩,问最终能否确定班级排名?
1、如何判断一个人的名次是否确定了呢?
就是 比他成绩好的人数 + 没他成绩好的人数总和 = 总人数(除自己)
2、根据这几组关系,如何判断一个人是否比另一个人的成绩好呢?
这就体现出 floyd 算法的另外一个用途:判断两点之间是否可以到达!
每加入一组关系就跑一遍 floyd(其实,只用这两个点作为中转点更新其他点就可以,见#
),如果两点之间的距离不是正无穷,就说明两点之间可达,也就是说:dist[x][y]!=1e9
说明 x 比 y 的成绩好。
如此,对于一个点,遍历其余所有点就可以得到:比该点成绩好的点数 和 比该点成绩差的点数。
3、如何判断出现了矛盾呢?
如果发现:从 x 能到达 y 并且从 y 也能到达 x(即,x 比 y 成绩好并且 y 比 x 成绩好),那就是出现矛盾了。
4、如何输出排好序的序列呢?
方法1:
开一个位置数组,如果一个点的位置确定了,那就将该点存到位置数组对应的位置上。
对应的位置就是能达到该点的点数+1(能到达该点的点都排在该点前面)
这样,如果所有的点都确定了,直接输出位置数组就行了!
方法2(2刷):
将所有点按照 能到达的点数 从小到大排序。然后依次输出编号。
#:
当图中只有一条边的权值变小时,没有必要跑完整的 floyd,只需要用这条边的两个端点分别作为中转点来更新其他点就行了。因为其他边没变,用其他点作为中转点不会有任何更新。
此外,需要注意只有边权变小时才能只用两个端点更新;如果边权变大了,需要重新初始化 dist,跑完整 floyd。因为边权变大了,之前用小边权更新的其他点不会因为这个变大的边来更新其值了。而边权变小的话,其他点会用这个小边权来更新。
二刷Code:(码风更好)
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
map<int,int> mp;
const int N = 210, mod = 1e9+7;
int T, n, m, k;
int a[N], dist[N][N];
PII ans[N];
void floyd(int x) //以 x 为中转点,更新其他点。
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
bool pd() //判断是否所有点都已确定
{
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=n;j++) if(dist[i][j]!=1e9) cnt++; //当前点能到达的点数
ans[i] = {cnt, i};
for(int j=1;j<=n;j++) if(i!=j && dist[j][i]!=1e9) cnt++; //能到达当前点的点数
if(cnt!=n) return 0;
}
sort(ans+1, ans+n+1);
return 1;
}
int main(){
while(cin>>n>>m && n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) dist[i][j] = 1e9;
int flag=0;
for(int i=1;i<=m;i++)
{
char a, t, b;cin>>a>>t>>b;
int x = a-'A'+1, y = b-'A'+1; //现在要加一条从 y 到 x 的边
if(!flag && dist[x][y] != 1e9) //发现已经从x能到y,出现矛盾
{
printf("Inconsistency found after %d relations.\n", i);
flag=1;
}
dist[y][x] = 1;
floyd(x), floyd(y); //分别以 x 和 y 为中转点更新其他点
if(!flag && pd()){ //发现所有点都已确定
printf("Sorted sequence determined after %d relations: ", i);
for(int i=1;i<=n;i++) cout<<char(ans[i].se+'A'-1);
printf(".\n");
flag=1;
}
}
if(!flag) printf("Sorted sequence cannot be determined.\n"); //无法确定
}
return 0;
}
Code:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=30;
int n,m,dist[N][N],ans[N];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main(){
while(cin>>n>>m&&n!=0&&m!=0)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j) dist[i][j]=1e9;
}
}
int flag=0;
for(int u=1;u<=m;u++)
{
char a,c,b;cin>>a>>c>>b;
int x=a-'A'+1,y=b-'A'+1;
if(x==y){ //注意特判 X<X 的情况。(感谢提醒!)
printf("Inconsistency found after %d relations.\n",u);
flag=1;break;
}
dist[x][y]=1; //之间有边,则说明x可传递到y
if(flag) continue;
floyd();
int anscnt=0;
for(int i=1;i<=n;i++)
{
int cnt=0,cnt1=0;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(dist[i][j]!=1e9&&dist[j][i]!=1e9){ //能相互到达,则矛盾
printf("Inconsistency found after %d relations.\n",u);
flag=1;break;
}
if(dist[j][i]!=1e9) cnt++; //能到达该点的个数
if(dist[i][j]!=1e9) cnt1++; //该点能到达的个数
}
if(flag==1) break;
if(cnt+cnt1==n-1) ans[cnt+1]=i,anscnt++; //如果能到达该点的个数+该点能到达的个数==总个数,则说明该点的位置已确定!存在该位置的数组中
}
if(anscnt==n&&!flag){ //所有的点都已经确定
printf("Sorted sequence determined after %d relations: ",u);
for(int i=1;i<=n;i++) cout<<char(ans[i]+'A'-1); //输出位置数组
cout<<"."<<endl;
flag=1;
}
}
//既不矛盾,又不能确定:
if(flag==0) cout<<"Sorted sequence cannot be determined."<<endl;
}
return 0;
}
代码不对,x=y特判时不能直接break,输入会错位的
妙啊
tql%%%
为什么“如果边权变大了,需要重新初始化 dist,跑完整 floyd”, 请问边权大了还需要初始化dist是什么意思呢
权值变大了,就要重新初始化 dist数组 为正无穷。
dist值
要么不变,要么因为这条边而更新变小。dist值
现在已经不是答案了。所以需要将所有点的dist值
重新初始化为正无穷,重新跑完整的floyd
。妙啊
x==y
的地方不能直接return 0
吧是的,已修改~
hack:
来自洛谷第一组数据
in:
out:
在输入时应特判一下 a b是否相等 本题数据有点弱
已更正,感谢兄弟提醒!抱拳!
读入到 $A<A$ 不应该直接 break,还应该把这组数据读完,不然下一组数据不是从 $A<A$ 后面开始读