hdu1824:http://acm.hdu.edu.cn/showproblem.php?pid=1824
题意：中文题。
题解：这一题建边要考虑两个限制条件，一个是队伍内部的，就是假如说 a,b,c,的话 a-->~b,b-->~a;a-->~c,c-->~a;同时b,c要留时候必须同时留下所以b-->c,c-->b;~b-->~c,~c-->~b;就是b留c需要留，c留b需要留，b不留c不要留，c不留留b不需要留，;;，然后是每一对的情况，直接建边就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,m,n;
const int N=;
const int M=;
const int INF=0xffffffff;
struct Edge{
int to,next;
} edge[M];
int cnt,u,v,dep,top,atype;
int dfn[N],low[N],vis[N],head[N],st[N],belong[N],in[N],out[N],sum[N];
//sum[i]记录第i个连通图的点的个数,in[i],out[i],表示缩点之后点的入度和初度。
void init(){
cnt=dep=top=atype=;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(belong,,sizeof(belong));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(sum,,sizeof(sum));
}
void addedge(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
} void Tarjan(int u){
dfn[u]=low[u]=++dep;
st[top++]=u;
vis[u]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
int j;
if(dfn[u]==low[u]){
atype++;
do{
j=st[--top];
belong[j]=atype;
sum[atype]++; //记录每个连通分量中点的个数
vis[j]=;
}
while(u!=j);
}
}
int fg[N],t1,t2,t3;
int main(){
while(~scanf("%d%d",&t,&m)){
int a,b,c;
int base=*t;
init();
for(int i=;i<t;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(b,c);
addedge(c,b);
addedge(b+base,c+base);
addedge(c+base,b+base);
addedge(a+base,b);
addedge(a+base,c);
addedge(b+base,a);
addedge(c+base,a);
}
while(m--){
scanf("%d%d",&a,&b);
addedge(a,b+base);
addedge(b,a+base);
}
for(int i=; i<*t; i++)
if(!dfn[i])
Tarjan(i);
bool flag=false;
for(int i=;i<*t;i++){
if(belong[i]==belong[i+base]){
flag=true;
break;
}
}
if(!flag)printf("yes\n");
else
printf("no\n");
} }
随机推荐
-
Swift3.0P1 语法指南——闭包
原档:https://developer.apple.com/library/prerelease/ios/documentation/Swift/Conceptual/Swift_Programmi ...
-
Wordpress 所有hoor列表
d 在插件加载的时候执行 wp_footer 加载页面底部时执行 admin_menu 加载管理员菜单时执行 wp_head 在body标签的开始添加html内容 after_setup_theme ...
-
python 深入模块和包
模块可以包含可执行语句以及函数的定义. 这些语句通常用于初始化模块. 它们只在 第一次 导入时执行.只在第一次导入的时候执行,第一次.妈蛋的第一次...后面再次导入就不执行了. [1](如果文件以脚本 ...
-
Lucene学习笔记： 四，Lucene索引过程分析
对于Lucene的索引过程,除了将词(Term)写入倒排表并最终写入Lucene的索引文件外,还包括分词(Analyzer)和合并段(merge segments)的过程,本次不包括这两部分,将在以后 ...
-
修改VC++2010界面左上角图标
(1)在Resource View中创建或者插入一个新的Icon资源,用于你想要的程序图标,假设ID号为IDI_ICON(这种图标要有16*16和32*32两种格式的,前者用于最小化和列表显示等,后者 ...
-
halcon与C#混合编程
halcon源程序: dev_open_window(0, 0, 512, 512, 'black', WindowHandle)read_image (Image, 'C:/Users/BadGuy ...
-
RedHat Linux 5.5安装JDK+Tomcat并部署Java项目
与大家分享下RedHat Linux 5.5安装JDK+Tomcat并部署Java项目的步骤,希望对大家有用. 1.下载并安装jdk 虚拟机中安装RedHat Linux 5.5 64位企业版, 这里 ...
-
jmeter- Java-POST接口使用get与json格式传参
在测试过程中发现各种接口传参形式,今天就来说说小编遇到的一种,接口请求方式为POST:URL传参以GET形式并携带JSON 可能这样诉说有不少同学不太理解. 如图: 上图所示就是一般get请求传参格式 ...
-
8.02-json_use
import json # 1.字符串和 dic list转换 # 字符串(json)----dict list data = '[{"name":"张三",& ...
-
PostgreSQL 之 yum安装 postgis 插件
版本说明: CentOS7.5 + PostgreSQL 10.5 参考资源: https://www.postgresql.org/download/linux/redhat/ http://dow ...