poj 3270 置换,循环节
SPFA的两个优化(转)

POJ 3660 传递闭包 warshall算法

scturtle posted @ 2010年8月16日 19:31 in algorithm , 1556 阅读

  初始化为-1,计算传递闭包过程中赢记为1,输记为0,最后检查传递闭包中无-1的行数或列数。

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int adj[101][101];
int tc[101][101];

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m,v,w,i,s,t,ans;
    scanf("%d%d",&n,&m);
    memset(adj,-1,sizeof(adj));
    for(i=1; i<=n; i++) adj[i][i]=1;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&v,&w);
        adj[v][w]=1;
    }

    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            tc[s][t]=adj[s][t];

    for(i=1;i<=n;i++)
        for(s=1;s<=n;s++)
            if(tc[s][i]>0)
                for(t=1;t<=n;t++)
                    if(tc[i][t]>0) {tc[s][t]=1;tc[t][s]=0;}

//    for(s=1; s<=n; s++)
//    {
//        for(t=1; t<=n; t++)
//            printf("%3d ",tc[s][t]);
//        cout<<endl;
//    }

    ans=n;
    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            if(tc[s][t]==-1)
            {
                ans--;
                break;
            }
    printf("%d\n",ans);
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter