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。

相关文章

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：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问
阅读更多...
poj 3159 （spfa差分约束最短路） poj 1201

poj 3159 （spfa差分约束最短路） poj 1201

poj 3159: 题意： 每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。 解析： 差分约束。 这个博客讲差分约束讲的比较好： http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码： #include <iostream>#include <cstdio>#i
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
poj 3169 spfa 差分约束

poj 3169 spfa 差分约束

题意： 给n只牛，这些牛有些关系。 ml个关系：fr 与 to 牛间的距离要小于等于 cost。 md个关系：fr 与 to 牛间的距离要大于等于 cost。 隐含关系： d[ i ] <= d[ i + 1 ] 解析： 用以上关系建图，求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码： #include <iostream>#include
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2