dp,图论
题意:输入n和m表示n个牛(从1到n标号),下面m个信息,A B,表示A牛能打赢B牛。现在要给所有的牛排名(按实力从高到低),问哪些牛的排名是可以确定的
如果知道由l个人能打赢自己,自己能打赢w个人,且l+w+1 = n的话,那么自己的排名就是可以确定的,所有转化为要求出,每个人,能打赢多少人,能被多少人打赢
建图: dp[i][j]=1表示i能打赢j,=0表示不确定他们之间的关系,然后类似floyd那样dp,
若dp[i][k]=1且dp[k][j]=1,则dp[i][j]=1
dp结束后扫描一次整个dp数组即可
被归为中等题,这不是水题么。。。。
#include#include #define N 110int dp[N][N];int n,m;int main(){ while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=0; i