2013年省赛I题
判断单向联通,用bfs
剪枝:从小到大跑,如果遇到之前跑过的点(也就是编号小于当前点的点),就o(n)传递关系。
bfs
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
int T;
int n,m,cnt;
int x,y;
bool b[][];
struct node{
int n;
node *next;
}*e[]; queue<int>q; void in(int &x){
int y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(int x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void push(int x,int y){
node *p;
p=new node();
p->n=y;
if(!e[x])
e[x]=p;
else{
p->next=e[x]->next;
e[x]->next=p;
}
} void bfs(int x){
q.push(x);
while(!q.empty()){
int t=q.front();
q.pop();
if(t<x){
For(i,,n)
if(b[t][i])
b[x][i]=;
}
else{
for(node *i=e[t];i;i=i->next)
if(!b[x][i->n]){
b[x][i->n]=;
q.push(i->n);
}
}
}
} bool judge(){
For(i,,n)
For(j,i+,n)
if(!b[i][j]&&!b[j][i])
return ;
return ;
} void clear(){
memset(b,,sizeof(b));
For(i,,)
e[i]=;
} int main(){
in(T);
while(T--){
clear();
in(n);in(m);
For(i,,m){
in(x);in(y);
push(x,y);
}
For(i,,n)
bfs(i);
printf("Case %d: ",++cnt);
if(judge())
printf("Kalimdor is just ahead\n");
else
printf("The Burning Shadow consume us all\n");
}
return ;
}
dfs更好写,队友比赛的时候不知道为啥T了
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
int T;
int n,m,cnt;
int x,y;
bool b[][];
struct node{
int n;
node *next;
}*e[]; queue<int>q; void in(int &x){
int y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(int x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void push(int x,int y){
node *p;
p=new node();
p->n=y;
if(e[x]==NULL)
e[x]=p;
else{
p->next=e[x]->next;
e[x]->next=p;
}
} // void bfs(int x){
// q.push(x);
// while(!q.empty()){
// int t=q.front();
// q.pop();
// if(t<x){
// For(i,1,n)
// if(b[t][i])
// b[x][i]=1;
// }
// else{
// for(node *i=e[t];i;i=i->next)
// if(!b[x][i->n]){
// b[x][i->n]=1;
// q.push(i->n);
// }
// }
// }
// } void dfs(int x,int f){
for(node *i=e[x];i;i=i->next)
if(!b[f][i->n]){
b[f][i->n]=;
dfs(i->n,f);
}
} bool judge(){
For(i,,n)
For(j,i+,n)
if(!b[i][j]&&!b[j][i])
return ;
return ;
} void clear(){
memset(b,,sizeof(b));
For(i,,)
e[i]=;
} int main(){
in(T);
while(T--){
clear();
in(n);in(m);
For(i,,m){
in(x);in(y);
push(x,y);
}
For(i,,n)
dfs(i,i);
printf("Case %d: ",++cnt);
if(judge())
printf("Kalimdor is just ahead\n");
else
printf("The Burning Shadow consume us all\n");
}
return ;
}
2013年省赛I题 Thrall’s Dream的更多相关文章
-
2013年山东省赛F题 Mountain Subsequences
2013年山东省赛F题 Mountain Subsequences先说n^2做法,从第1个,(假设当前是第i个)到第i-1个位置上哪些比第i位的小,那也就意味着a[i]可以接在它后面,f1[i]表示从 ...
-
2013年省赛H题
2013年省赛H题你不能每次都快速幂算A^x,优化就是预处理,把10^9预处理成10^5和10^4.想法真的是非常巧妙啊N=100000构造两个数组,f1[N],间隔为Af2[1e4]间隔为A^N,中 ...
-
HDU 4816 Bathysphere (2013长春现场赛D题)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4816 2013长春区域赛的D题. 很简单的几何题,就是给了一条折线. 然后一个矩形窗去截取一部分,求最 ...
-
HDU 4762 Cut the Cake (2013长春网络赛1004题,公式题)
Cut the Cake Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tota ...
-
HDU 4768 Flyer (2013长春网络赛1010题,二分)
Flyer Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submi ...
-
HDU 4758 Walk Through Squares (2013南京网络赛1011题,AC自动机+DP)
Walk Through Squares Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Oth ...
-
HDU 4738 Caocao&#39;s Bridges (2013杭州网络赛1001题,连通图,求桥)
Caocao's Bridges Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) ...
-
2013杭州现场赛B题-Rabbit Kingdom
杭州现场赛的题.BFS+DFS #include <iostream> #include<cstdio> #include<cstring> #define inf ...
-
HDU 4759 Poker Shuffle(2013长春网络赛1001题)
Poker Shuffle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tot ...
随机推荐
-
[1]IP地址查询
今天起开始玩百度APIStore里面的免费API.以前用过的有12306的:数据.接口,有时间整理出来,12306的有点乱就是了.还有扇贝以及有道的API,之前用在留言板里自动翻译,公司用过百度地图以 ...
-
删:Centos 7安装Nginx 1.8
[CentOS 7] 安装nginx! 首先进行 nginx yum Nginx安装记录 注意:如果用源码安装,nginx配置时需要指定--with-pcer对应的压缩包路径,如果使用二进制安装不需要 ...
-
UIViewCotroller 的生命周期函数
Viewcontroller 的所有生命周期函数 重写时 一定要先写 父类 方法 就是(super +生命周期函数) LoadView ViewDidLoad ViewDidUnload: 在iOS ...
-
查看进程所用的内存(使用GetWindowThreadProcessId取得进程ID,OpenProcess打开进程和GetProcessMemoryInfo取得内存信息)
// function GetProcessMemorySize(_sProcessName: string; var _nMemSize: Cardinal): Boolean; var l_nWn ...
-
四色GDOI&;GDOI2015滚粗记
好吧自己太弱写不了什么四色NOI只能学学别人写个四色GDOI了...首先自己还是太弱所以就被学校卡了个名额就进不了省队了QAQ.自己GDOI觉得考得不错可是NOIP毕竟少了人家5分根本追不上去好不QA ...
-
iOS 生成随机字符串 从指定字符串随机产生n个长度的新字符串
随机字符串 - 生成指定长度的字符串 -(NSString *)randomStringWithLength:(NSInteger)len { NSString *letters = @"a ...
-
freemarker写select组件报错总结(一)
1.具体错误如下 六月 25, 2014 11:26:29 下午 freemarker.log.JDK14LoggerFactory$JDK14Logger error 严重: Template pr ...
-
windows10不能修改hosts解决方案(亲测)
hosts文本解释: 有时候我们要破解一些软件与服务器通讯,所以通常都需要更改Hosts文件来达到目的,XP系统可以直接修改保存,但是Win10系统却提示没有权限去修改,那么我们要怎样办呢,我们修改的 ...
-
玩转X-CTR100 l STM32F4 l 基础例程printf、LED、蜂鸣器、拨码开关、位带操作
我造*,你造车,创客一起造起来!塔克创新资讯[塔克社区 www.xtark.cn ][塔克博客 www.cnblogs.com/xtark/ ] 本文介绍X-CTR100控制器基础板载资源 ...
-
Ubuntu 11.10 H3C iNode 客户端安装
下载客户端,放到桌面 双击打开,点击解压缩 Ctrl+Alt+T打开终端,依次输入以下代码并回车 代码: cd 桌面sudo cp iNodeClient /usr -Rcd /usr/iNodeCl ...