UVA10766(스패닝 트리 수)

1749 단어
코드 변경 템플릿은 그다지 고쳐지지 않았다.다른 사람이 고친 것을 보니 여전히 좀 모르겠다.
#include
#include
#include
#include
using namespace std;
const int MAX=55;
typedef long long int ll;

int deg[MAX];
int g[MAX][MAX];
ll b[MAX][MAX];

ll Det(int n){
    int i,j,k;
    ll ret = 1;
    for(i=2;i<=n;i++){
        for(j = i+1;j <= n;j++){
            while(b[j][i]){  //        
                ll tmp=b[i][i]/b[j][i];
                for(k = i;k <= n;k++)
                    b[i][k] -= tmp*b[j][k];
                for(k=i;k<=n;k++)
                    swap(b[i][k],b[j][k]);  //  
                ret = -ret;
            }
        }
        if(!b[i][i]) return 0;
        ret *= b[i][i];
    }
    if(ret < 0) ret = -ret;
    return ret;

}

int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k) != EOF){
        int u,v;
        memset(deg,0,sizeof(deg));
        memset(g,0,sizeof(g));
        memset(b,0,sizeof(b));
        while(m--){
            scanf("%d%d",&u,&v);
            g[u][v] = 1;g[v][u] = 1;  //      

        }

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(!g[i][j] && i != j){
                     b[i][j] = -1;
                     deg[i]++;
                }
            }
        }
        for(int i = 1;i <= n;i++){
            b[i][i] = deg[i];     //      
        }
          //              
    /*
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf(" %d",b[i][j]);
            }puts("");
        }*/

        printf("%lld
",Det(n)); } return 0; }

좋은 웹페이지 즐겨찾기