题意：
序列长度为n,但是具体的数值不知道。给出了m对关系( x , y )，表示序列中a x > a y。问每个数能否作为中位数。
n m o d 2 = = 1 & & n < = 100
思路1：
建图，对于关系( x , y )建立y − > x的有向边。
先考虑不合法的情况，如果有环(自环)的话说明不合法，跑一遍拓扑排序，看最后入队过的元素是否等于关系里出现过的元素。不能跟所有的点比较，因为有的点可能在关系里没出现过，不具有大小关系。
如果一个点能够作为中位数的话，说明严格大于他的点< = n / 2并且严格小于他的点也< = n / 2。如果严格大于他的点< = n / 2，就可以将不确定关系的放到大于他的地方。后者也同理。
所以，对于一个关系( x , y )，建立图一x − > y，图二y − > x。将该点的出点放入队列里，跑b f s就可以了，记录入队过的点的个数。
注：也可以将该点放入队列里，最后入队的点的个数要− 1，即减去这个点本身。
将该点放入队列的写法。
bool bfs1(int s){ for(int i=1;i<=n;i++) vis[i]=0; queue<int>q; int ans=0; q.push(s);vis[s]=1; while(!q.empty()){ int t=q.front();q.pop(); ans++; for(int tt:g1[t]){ if(!vis[tt]) q.push(tt),vis[tt]=1; } } ans--; return ans<=n/2; } bool bfs2(int s){ for(int i=1;i<=n;i++) vis[i]=0; queue<int>q; int ans=0; q.push(s);vis[s]=1; while(!q.empty()){ int t=q.front();q.pop(); ans++; for(int tt:g2[t]){ if(!vis[tt]) q.push(tt),vis[tt]=1; } } ans--; return ans<=n/2; }
代码1：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll #define x first #define y second inline ll read() { ll 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*10+ch-'0';ch=getchar();} return x*f; } #define read read() char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f,mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=1100,maxm=3e6+7; const double PI = atan(1.0)*4; vector<int>g1[maxn],g2[maxn]; int n,m,din1[maxn],din2[maxn],din[maxn]; bool vis[maxn]; map<int,bool>mp; bool topsort(){ queue<int>q; int ans=0; for(int i=1;i<=n;i++){ if(!din1[i]&&mp[i]) q.push(i); din[i]=din1[i]; } while(!q.empty()){ int t=q.front();q.pop(); ans++; for(int tt:g1[t]){ --din[tt]; if(!din[tt]) q.push(tt); } } int cnt=0; for(int i=1;i<=n;i++) if(mp[i]) cnt++; // cout<<ans<<" "<<cnt<<endl; return ans==cnt; } bool bfs1(int s){ for(int i=1;i<=n;i++) vis[i]=0; queue<int>q; int ans=0; for(int tt:g1[s]){ q.push(tt);vis[tt]=1; } while(!q.empty()){ int t=q.front();q.pop(); ans++; for(int tt:g1[t]){ if(!vis[tt]) q.push(tt),vis[tt]=1; } } return ans<=n/2; } bool bfs2(int s){ for(int i=1;i<=n;i++) vis[i]=0; queue<int>q; int ans=0; for(int tt:g2[s]){ q.push(tt);vis[tt]=1; } while(!q.empty()){ int t=q.front();q.pop(); ans++; for(int tt:g2[t]){ if(!vis[tt]) q.push(tt),vis[tt]=1; } } return ans<=n/2; } int main(){ int _=read; while(_--){ mp.clear(); n=read,m=read; bool flag=0; for(int i=1;i<=n;i++){ din1[i]=din2[i]=0; g1[i].clear();g2[i].clear(); } for(int i=1;i<=m;i++){ int u=read,v=read; if(u==v) flag=1; g1[u].push_back(v); din1[v]++; g2[v].push_back(u); din2[u]++; mp[u]=mp[v]=1; } if(!topsort()||flag){ for(int i=1;i<=n;i++) printf("0"); puts(""); } else{ for(int i=1;i<=n;i++){ if(!mp[i]){ printf("1");continue; } if(bfs1(i)&&bfs2(i)) printf("1"); else printf("0"); //cout<<i<<" "<<bfs1(i)<<" "<<bfs2(i)<<"\n"; } puts(""); } } return 0; } /* */
思路2：
可以直接用floyd传递大小关系，判断每个点的入度和出度是不是都< n / 2
不合法的情况，首先是自环，然后是m p [ i ] [ j ] , m p [ j ] [ i ]同时为1，说明两者出现了矛盾。
代码2：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll #define x first #define y second inline ll read() { ll 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*10+ch-'0';ch=getchar();} return x*f; } #define read read() char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f,mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=1100,maxm=3e6+7; const double PI = atan(1.0)*4; int mp[1100][1100],n,m; int din[maxn],dout[maxn]; int main(){ int _=read; while(_--){ n=read,m=read; memset(mp,0,sizeof mp); memset(din,0,sizeof din); memset(dout,0,sizeof dout); bool flag=0; for(int i=1;i<=m;i++){ int u=read,v=read; if(u==v) flag=1; mp[u][v]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]|=mp[i][k]&mp[k][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]&&mp[j][i]) flag=1; if(flag){ for(int i=1;i<=n;i++) printf("0"); puts(""); continue; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&mp[i][j]) din[j]++,dout[i]++; for(int i=1;i<=n;i++) if(din[i]<=n/2&&dout[i]<=n/2) printf("1"); else printf("0"); puts(""); } return 0; } /* */
![[计蒜客] ACM-ICPC 2018 南京赛区网络预赛 | 部分题解 | 线段树 + 线性筛 + 最短路（上）](https://ucc.alicdn.com/pic/developer-ecology/d3c2fdd70f4d439380a044791e251bd3.png?x-oss-process=image/resize,h_160,m_lfit)
