技巧
1 对于每一列,可以直接sort,然后判断谁在谁的前面,但是多个这样的关系要怎么判断是否矛盾??
也就是判断前后关系是否矛盾,对吧,使用topsort,就可以确定谁在谁的前面。
2 对于多个相同的点,比如 1 1 1 2 2 2如果直接建图,需要建立9条边,也就是左边相数m1*右边相等数m2
这里可以采用一个中间点的方式,这样子是m1+m2
这样可以保证边的数量很小
3 怎么确定那种谁和谁之间建立边,怎么样代码优雅一点,设立一个pre,然后每次对pre进行更新
代码
//设立一个超级起源地,来代替多个点
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;
using pii=pair<int,int>;
#define fi first
#define se second
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
vector<int>g[M<<1];
vector<pii>f;
int in[M<<1];
int n,m,tot;
bool topsort() {
queue<int>q;
for(int i=1;i<=tot;i++)
if(in[i]==0)q.push(i);
while(!q.empty()) {
int now=q.front();
q.pop();
for(auto to:g[now])
if(--in[to]==0)q.push(to);
}
for(int i=1;i<=m;i++)
if(in[i])return 0;
return 1;
}
int main() {
n=read(),m=read();
tot=m;
for(int i=1;i<=n;i++) {
vector<pii>v;
for(int j=1;j<=m;j++) {
int x=read();
if(x)v.push_back({x,j});
}
sort(v.begin(),v.end());
int pre=0;
//这个处理很奇妙呀
for(int j=1;j<v.size();j++) {
if(v[j-1].fi<v[j].fi) {
++tot;
for(int k=pre;k<j;k++) {
g[v[k].se].push_back(tot);
in[tot]++;
}
pre=j;
}
if(pre!=0) {
g[tot].push_back(v[j].se);
in[v[j].se]++;
}
}
if(v.size())f.push_back({v.front().fi,v.back().fi});
}
if(topsort()==0)return cout<<"No\n",0;
sort(f.begin(),f.end());
for(int i=1;i<f.size();i++)
if(f[i].fi<f[i-1].se)return cout<<"No\n",0;
cout<<"Yes\n";
return 0;
}
标签:ch,--,int,abc,277,using,getchar
From: https://www.cnblogs.com/basicecho/p/16998802.html