首页 > 其他 > 详细

UVA 10766 Organising the Organisation

时间:2017-08-23 15:25:50      阅读:272      评论:0      收藏:0      [点我收藏+]

https://vjudge.net/problem/UVA-10766

 

题意:

n个员工,除总经理外每个人只能有一个直接上级

有m对人不能成为直接的上下级关系

规定k为总经理

问员工分级方案

 

无向图生成树的个数与根无关

所以直接用矩阵树定理即可

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,C[51][51];
bool can[51][51];
int main()
{
    int n,m,k,u,v;
    LL t,ans;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        memset(C,0,sizeof(C));
        memset(can,false,sizeof(can));
        while(m--)
        {
            scanf("%d%d",&u,&v);
            can[u][v]=can[v][u]=true;
        }
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
                if(!can[i][j]) 
                {
                    C[i-1][j-1]=C[j-1][i-1]=-1;
                    C[i-1][i-1]++;
                    C[j-1][j-1]++;
                }
        ans=1;
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
                while(C[j][i])
                {
                    t=C[i][i]/C[j][i];
                    for(int k=i;k<n;k++) C[i][k]-=C[j][k]*t;
                    for(int k=i;k<n;k++) swap(C[i][k],C[j][k]);
                    ans=-ans;
                }
            ans*=C[i][i];
            if(!ans) break;
        }
        if(ans<0) ans=-ans;
        printf("%lld\n",ans);    
    }
}

 

UVA 10766 Organising the Organisation

原文:http://www.cnblogs.com/TheRoadToTheGold/p/7418326.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!