洛谷P3043 [USACO12JAN]牛联盟Bovine Alliance
P3043 [USACO12JAN]牛联盟Bovine Alliance
题目描述
Bessie and her bovine pals from nearby farms have finally decided that they are going to start connecting their farms together by trails in an effort to form an alliance against the farmers. The cows in each of the N (1 <= N <= 100,000) farms were initially instructed to build a trail to exactly one other farm, for a total of N trails. However months into the project only M (1 <= M < N) of these trails had actually been built.
Arguments between the farms over which farms already built a trail now threaten to split apart the cow alliance. To ease tension, Bessie wishes to calculate how many ways the M trails that exist so far could have been built. For example, if there is a trail connecting farms 3 and 4, then one possibility is that farm 3 built the trail, and the other possibility is that farm 4 built the trail. Help Bessie by calculating the number of different assignments of trails to the farms that built them, modulo 1,000,000,007. Two assignments are considered different if there is at least one trail built by a different farm in each assignment.
给出n个点m条边的图,现把点和边分组,每条边只能和相邻两点之一分在一组,点可以单独一组,问分组方案数。
输入输出格式
输入格式:
Line 1: Two space-separated integers N and M
- Lines 2..1+M: Line i+1 describes the ith trail. Each line contains two space-separated integers u_i and v_i (1 <= u_i, v_i <= N, u_i != v_i) describing the pair of farms connected by the trail.
输出格式:
- Line 1: A single line containing the number of assignments of trails to farms, taken modulo 1,000,000,007. If no assignment satisfies the above conditions output 0.
输入输出样例
说明
Note that there can be two trails between the same pair of farms.
There are 6 possible assignments. Letting {a,b,c,d} mean that farm 1 builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4 builds trail d, the assignments are:
{2, 3, 4, 5}
{2, 3, 5, 4}
{1, 3, 4, 5}
{1, 3, 5, 4}
{1, 2, 4, 5}
{1, 2, 5, 4}
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstdlib>
#define maxn 100010
#define mod 1000000007
using namespace std;
int n,m,num,head[maxn];
long long ans=;
bool vis[maxn];
struct node{
int to,pre;
}e[maxn*];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
void bfs(int s){
queue<int>q;
q.push(s);vis[s]=;
int cnt1=,cnt2=;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
cnt2++;
if(!vis[to]){
vis[to]=;
cnt1++;
q.push(to);
}
}
}
cnt2/=;
if(cnt1==cnt2)ans=(2LL*ans)%mod;
else if(cnt1-==cnt2)ans=(1LL*cnt1*ans)%mod;
else {puts("");exit();}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
Insert(x,y);Insert(y,x);
}
for(int i=;i<=n;i++){
if(!vis[i])bfs(i);
}
cout<<ans;
}
最新文章
- 创建ASP.NET Core MVC应用程序(3)-基于Entity Framework Core(Code First)创建MySQL数据库表
- SQL MD5加密
- Install Slax on USB device (Slax U 盘安装)
- android之imgView插件的使用
- Paramiko 模块使用
- Java基础知识强化19:Java中switch分支语句
- 关于sys、system、sysman等在EM中登录的问题
- Java开发中常见的危险信号(上)
- LB 负载均衡的层次结构(转)
- ORACLE 中的 锁 介绍
- Java笔记(二十) 注解
- 4,postman和newman的联合使用
- 快速傅里叶变换(FFT)
- FastCGI sent in stderr: ";PHP Warning: simplexml_load_string(): Entity: line 1: parser error : Start tag expected, &#39;&;lt;&#39; not found in
- 【专栏学习】APM——异步编程模型(.NET不推荐)
- React系列文章:无状态组件生成真实DOM结点
- Java知识点-判断null、空字符串和空格
- 课堂Beta发布
- 搭建持续集成单元测试平台(Jenkins+Ant+Java+Junit+SVN)
- python输出格式化及函数format