2013年省赛I题 Thrall’s Dream

时间:2023-02-25 13:08:00

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的更多相关文章

  1. 2013年山东省赛F题 Mountain Subsequences

    2013年山东省赛F题 Mountain Subsequences先说n^2做法,从第1个,(假设当前是第i个)到第i-1个位置上哪些比第i位的小,那也就意味着a[i]可以接在它后面,f1[i]表示从 ...

  2. 2013年省赛H题

    2013年省赛H题你不能每次都快速幂算A^x,优化就是预处理,把10^9预处理成10^5和10^4.想法真的是非常巧妙啊N=100000构造两个数组,f1[N],间隔为Af2[1e4]间隔为A^N,中 ...

  3. HDU 4816 Bathysphere (2013长春现场赛D题)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4816 2013长春区域赛的D题. 很简单的几何题,就是给了一条折线. 然后一个矩形窗去截取一部分,求最 ...

  4. 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 ...

  5. HDU 4768 Flyer (2013长春网络赛1010题,二分)

    Flyer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submi ...

  6. HDU 4758 Walk Through Squares (2013南京网络赛1011题,AC自动机&plus;DP)

    Walk Through Squares Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Oth ...

  7. HDU 4738 Caocao&&num;39&semi;s Bridges (2013杭州网络赛1001题,连通图,求桥)

    Caocao's Bridges Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  8. 2013杭州现场赛B题-Rabbit Kingdom

    杭州现场赛的题.BFS+DFS #include <iostream> #include<cstdio> #include<cstring> #define inf ...

  9. HDU 4759 Poker Shuffle(2013长春网络赛1001题)

    Poker Shuffle Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tot ...

随机推荐

  1. &lbrack;1&rsqb;IP地址查询

    今天起开始玩百度APIStore里面的免费API.以前用过的有12306的:数据.接口,有时间整理出来,12306的有点乱就是了.还有扇贝以及有道的API,之前用在留言板里自动翻译,公司用过百度地图以 ...

  2. 删:Centos 7安装Nginx 1&period;8

    [CentOS 7] 安装nginx! 首先进行 nginx yum Nginx安装记录 注意:如果用源码安装,nginx配置时需要指定--with-pcer对应的压缩包路径,如果使用二进制安装不需要 ...

  3. UIViewCotroller 的生命周期函数

    Viewcontroller 的所有生命周期函数 重写时 一定要先写 父类 方法 就是(super  +生命周期函数) LoadView ViewDidLoad ViewDidUnload: 在iOS ...

  4. 查看进程所用的内存(使用GetWindowThreadProcessId取得进程ID,OpenProcess打开进程和GetProcessMemoryInfo取得内存信息)

    // function GetProcessMemorySize(_sProcessName: string; var _nMemSize: Cardinal): Boolean; var l_nWn ...

  5. 四色GDOI&amp&semi;GDOI2015滚粗记

    好吧自己太弱写不了什么四色NOI只能学学别人写个四色GDOI了...首先自己还是太弱所以就被学校卡了个名额就进不了省队了QAQ.自己GDOI觉得考得不错可是NOIP毕竟少了人家5分根本追不上去好不QA ...

  6. iOS 生成随机字符串 从指定字符串随机产生n个长度的新字符串

    随机字符串 - 生成指定长度的字符串 -(NSString *)randomStringWithLength:(NSInteger)len { NSString *letters = @"a ...

  7. freemarker写select组件报错总结(一)

    1.具体错误如下 六月 25, 2014 11:26:29 下午 freemarker.log.JDK14LoggerFactory$JDK14Logger error 严重: Template pr ...

  8. windows10不能修改hosts解决方案(亲测)

    hosts文本解释: 有时候我们要破解一些软件与服务器通讯,所以通常都需要更改Hosts文件来达到目的,XP系统可以直接修改保存,但是Win10系统却提示没有权限去修改,那么我们要怎样办呢,我们修改的 ...

  9. 玩转X-CTR100 l STM32F4 l 基础例程printf、LED、蜂鸣器、拨码开关、位带操作

    我造*,你造车,创客一起造起来!塔克创新资讯[塔克社区 www.xtark.cn ][塔克博客 www.cnblogs.com/xtark/ ]      本文介绍X-CTR100控制器基础板载资源 ...

  10. Ubuntu 11&period;10 H3C iNode 客户端安装

    下载客户端,放到桌面 双击打开,点击解压缩 Ctrl+Alt+T打开终端,依次输入以下代码并回车 代码: cd 桌面sudo cp iNodeClient /usr -Rcd /usr/iNodeCl ...