题意：有两组食物，分别有\(n\)个和\(m\)个。 给定\(n\times m\)的一个表格，其中\(a[i][j]\)表示第一组第\(i\)个食物和第二组第\(j\)个食物的美味度大小关系。 请问是否能给出一组美味度方案。如果有，请给出美味度最大值最小的方案。如果没有，请输出No.
先膜LCJ 本题如果数据出小一点就是差分约束系统的裸题。 但是到了现在的数据大小，差分约束无法承受，所以考虑用并查集+拓扑排序解决。 把=的食物用并查集并起来。然后对于>和<的情况，如果这俩元素在一个联通块里，显然不能构造。 否则，如果\(a[i][j]= '<'\)就从\(i\)的连通块向\(j\)连一条边，反之亦然。 然后对联通块跑拓扑排序即可。注意有环也不能构造。正确性很显然：对于\(v\)，如果被删成了入度\(=0\)，那么上一次它只需要满足\(u\)的限制即可。 故\(value[v] = value[u] + 1\).
/** * @Author: Mingyu Li * @Date: 2019-03-09T22:42:11+08:00 * @Email: class11limingyu@126.com * @Filename: c1131D.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-10T06:53:10+08:00 */ #include <bits/stdc++.h> #define tpname typename #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } const int N = 1000 + 5; int f[N + N]; int find(int x) { return x == f[x] ? f[x] : f[x] = find(f[x]); } std::vector <int> v[N + N] , Graph[N + N]; std::map <std::pair<int,int>,int> alr; char a[N][N]; int n , m; int merge(int u , int v) { f[find(u)] = find(v); } int rf; int degree[N + N] , ans[N + N]; void Link(int u , int v) { if(u == v) { rf = 1; return ; } if(alr[{u , v}]) return ; alr[{u , v}] = 1; Graph[u].push_back(v); ++degree[v]; } int main() { sc(n , m); Go(i , 1 , n) scanf("%s" , (a[i] + 1)); Go(i , 1 , n+m) f[i] = i; Go(i , 1 , n) Go(j , 1 , m) if(a[i][j] == '=') merge(i , n+j); std::vector <int> v1; Go(i , 1 , n+m) v[find(i)].push_back(i) , v1.push_back(find(i)); Go(i , 1 , n) Go(j , 1 , m) { if(a[i][j] == '<') Link(find(i) , find(n+j)); else if(a[i][j] == '>') Link(find(n+j) , find(i)); } if(rf) { puts("No"); return 0; } std::queue <std::pair <int , int> > Q; sort(v1.begin() , v1.end()); int m1 = unique(v1.begin() , v1.end()) - v1.begin(); std::vector <int> v2; Go(i , 0 , m1-1) if(!degree[v1[i]]) { Q.push({v1[i] , 1}); v2.push_back(v1[i]); for(auto fix : v[v1[i]]) ans[fix] = 1; } while(!Q.empty()) { std::pair < int , int > x = Q.front(); Q.pop(); int u = x.first , va = x.second; for(auto vv : Graph[u]) { degree[vv]--; if(!degree[vv]) { degree[vv] = 0; Q.push({vv , va + 1}); v2.push_back(vv); } } } Go(i , 0 , v2.size() - 1) { for(auto fix : v[v2[i]]) ans[fix] = i + 1; } int ans1 = 0; Go(i , 1 , n+m) ans1 += (degree[find(i)] == 0); //std::cerr << "\n"; if(ans1 != n+m) { puts("No"); return 0; } std::cout << "Yes\n"; Go(i , 1 , n) std::cout << ans[i] << " "; std::cout << "\n"; Go(i , 1 , m) std::cout << ans[n + i] << " "; std::cout << "\n"; return 0; }转载于:https://www.cnblogs.com/LiM-817/p/10887242.html
相关资源：数据结构—成绩单生成器