HDU1811 Rank of Tetris 拓扑排序+并查集 OR 差分约束最短路+并查集

2024-03-02 08:18
文章标签 排序 查集 拓扑 短路 差分 约束 rank tetris hdu1811

本文主要是介绍HDU1811 Rank of Tetris 拓扑排序+并查集 OR 差分约束最短路+并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题意：就是给你一堆关系，看能不能排出个确定的顺序

做法：

1. 拓扑排序+并查集

应该很容易想到的一种思路，大于小于建立单向边。对于相等的呢，就把他们缩成一个点。就用并查集缩成一个点就行了

  • 入度为0进队列，队列数目>1，有冲突
  • 没有遍历完，信息不完整
  • 不然，输出OK
//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const long long inFF = 9223372036854775807;
const int mod=1e9+7;
const int maxn=1e5+5;
struct nod
{int x,y;
}a[maxn];
vector<int> v[maxn];
int n,m;
int f[maxn],in[maxn];
int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}
void init()
{for(int i=0;i<=n;i++) f[i]=i;for(int i=0;i<=n;i++) v[i].clear(),in[i]=0;
}
int main()
{while(cin>>n>>m){if(m==0) {if (n == 0 || n == 1) puts("OK");else puts("UNCERTAIN");continue;}int cnt=0;int x,y;char s[2];init();for(int i=1;i<=m;i++){scanf("%d%s%d",&x,s,&y);if(s[0]=='='){x=find(x);y=find(y);if(x!=y) f[x]=y;}else if(s[0]=='>') a[++cnt]=nod{x,y};else a[++cnt]=nod{y,x};}int fg=0;for(int i=1;i<=cnt;i++){int x=find(a[i].x);int y=find(a[i].y);if(x==y){fg=1;break;}v[x].push_back(y);in[y]++;}queue<int> q;int num=0,d=0;for(int i=0;i<n;i++){if(find(i)==i){d++;if(in[i]==0) q.push(i);}}if(fg) {puts("CONFLICT");continue;}while(!q.empty()){if(q.size()>1) fg=1;//信息不足int u=q.front();q.pop();num++;for(int x:v[u]){in[x]--;if(in[x]==0)q.push(x);}}if(num!=d) puts("CONFLICT");else if(fg==1) puts("UNCERTAIN");else puts("OK");}
}

2.差分约束最短路+并查集

因为上边所述的关系属于差分约束条件，考虑用差分约束来搞。

怎么构造差分直接跳——>点我，用并查集来判断是否有没有信息不完整

造完图后就是一个最短路判环

如果有负环，冲突

如果

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const long long inFF = 9223372036854775807;
const int mod=1e9+7;
const int maxn=1e5+5;
int d[maxn],vis[maxn],f[maxn],cnt[maxn];
int head[maxn],sign;
struct node
{int to,p,val;
}edge[maxn];
int n,m,fg;
void init()
{for(int i=0;i<=n;i++){f[i]=i;head[i]=-1;cnt[i]=0;}sign=0;
}
void add(int u,int v,int val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;
}
int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}
void meger(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[x]=y;//x->y 有一点疑惑，不知道为什么这么合并，但是确实能判断信息是否完整
}
void spfa()
{for(int i=0;i<=n;i++) d[i]=inff,vis[i]=0,cnt[i]=0;d[0]=0;queue<int> q;q.push(0);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;if(d[v]>edge[i].val+d[u]){d[v]=edge[i].val+d[u];if(!vis[v]){vis[v]=1;if(++cnt[v]>n){cout<<"CONFLICT"<<endl;return ;}q.push(v);}}}}if(fg) cout<<"UNCERTAIN"<<endl;else cout<<"OK"<<endl;
}
int main()
{while(cin>>n>>m){int x,y;char ch;init();for(int i=1;i<=m;i++){scanf("%d %c %d",&x,&ch,&y);x++,y++;meger(x,y);if(ch=='=') add(y,x,0),add(x,y,0);else if(ch=='>') add(x,y,-1);else if(ch=='<') add(y,x,-1);}for(int i=1;i<=n;i++) add(0,i,0);int sum=0;fg=0;for(int i=1;i<=n;i++)if(i==find(i)) sum++;if(sum>1) fg=1;spfa();}
}

 

这篇关于HDU1811 Rank of Tetris 拓扑排序+并查集 OR 差分约束最短路+并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/765479。

相关文章

Spring排序机制之接口与注解的使用方法

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri
阅读更多...
大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
SQL中的外键约束

SQL中的外键约束

外键约束用于表示两张表中的指标连接关系。外键约束的作用主要有以下三点： 1.确保子表中的某个字段（外键）只能引用父表中的有效记录2.主表中的列被删除时，子表中的关联列也会被删除3.主表中的列更新时，子表中的关联元素也会被更新 子表中的元素指向主表 以下是一个外键约束的实例展示
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
阅读更多...
poj 1502 MPI Maelstrom（单源最短路dijkstra）

poj 1502 MPI Maelstrom（单源最短路dijkstra）

题目真是长得头疼，好多生词，给跪。 没啥好说的，英语大水逼。 借助字典尝试翻译了一下，水逼直译求不喷 Description： BIT他们的超级计算机最近交货了。（定语秀了一堆词汇那就省略吧再见） Valentine McKee的研究顾问Jack Swigert，要她来测试一下这个系统。 Valentine告诉Swigert：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2