[HDOJ3357 Stock Chase]维护传递闭包

【题目大意】

给出N个点，按读入顺序加入有向边，然后如果某条边加入以后，形成了环，那么就不加这条边。

问最后有多少条边不被加。

【算法分析】

维护一个闭包，如果加入边x->y，且y本来就可以到达x，那么这条边不加。

否则更新闭包。

复杂度O(MIN(n^4,T*n^2))。

【其它】

正解不知道是啥。。。这种方法明显水过，明天再问问人。。。

【CODE】

#include #include #include #include #include using namespace std;

int Tc=0,n,m,i,j,k,x,y,ans;
bool map[255][255];

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (;;){
        Tc++;
        scanf("%d%d",&n,&m);
        if (!n && !m) break;
        memset(map,false,sizeof(map));
        for (i=1;i<=n;i++) map[i][i]=true;
        for (ans=0,k=1;k<=m;k++){
            scanf("%d%d",&x,&y);
            if (map[y][x]) ans++;
            else if (!map[x][y]){
                map[x][y]=true;
                for (i=1;i<=n;i++)
                  for (j=1;j<=n;j++)
                    if (map[i][x] && map[y][j]) map[i][j]=true;
            }   
        }   
        printf("%d. %dn",Tc,ans);
    }   
}