zoj 4124 "Median" （思维？假的图论？）

传送门

来源：2019 年“浪潮杯”第十届山东省 ACM 省赛

题意：

　　对于一个包含n个数的（n为奇数）序列val[ ]，排序后的 val[ (n+1) / 2 ] 定义为 median；

　　有 n 个数，并有 m 组关系，对于第 i 组关系 a_i,b_i 代表第 val[a_i] > val[b_i]；

　　但并没有给出具体的数值；

　　输出一个包含 n 个元素的数组 s[ ] ；

　　让你判断第 i 个数 val[ i ]是可能为中位数，如果是，第 i 位为 1；

　　如果不是，第 i 位为 0；

　　输出 n 个数，其中第 i 个数为 0 或 1，含义如上；

题解：

　　首先，特判两种情况：

　　　　①a_i = b_i；

　　　　②给出的 m 个关系有环；

　　对于这两种情况，输出 n 个 0；

　　除了这两种情况外，就是一个有向无环图；

　　如何判断第 i 位是否为 median 呢？

　　搜索：

　　正向搜索比第 i 个数小的数的总个数 tot1；

　　反向搜索比第 i 个数大的数的总个数 tot2；

　　那么，还剩下 res = n-(tot1+tot2+1) 个数；

　　如果 res ≥ |tot1-tot2|，那么第 i 个数就是中位数；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define mem(a,b) memset(a,b,sizeof(a))

 const int maxn=1e4+;

 int n,m;

 int num;

 int head[maxn];

 bool vis[];

 bool isCir;

 char s[];

 struct Edge

 {

     int to;

     int next;

 }G[maxn<<];

 void addEdge(int u,int v)

 {

     G[num]={v,head[u]};

     head[u]=num++;

 }

 struct SCC

 {

     vector<int >vs;

     void DFS(int u)

     {

         vis[u]=true;

         for(int i=head[u];~i;i=G[i].next)

         {

             int v=G[i].to;

             if((i&) || vis[v])

                 continue;

             DFS(v);

         }

         vs.push_back(u);

     }

     void RDFS(int u,int k)

     {

         vis[u]=true;

         for(int i=head[u];~i;i=G[i].next)

         {

             int v=G[i].to;

             if(!(i&) || vis[v])

                 continue;

             RDFS(v,k);

         }

     }

     int scc()

     {

         vs.clear();

         mem(vis,false);

         for(int i=;i <= n;++i)

             if(!vis[i])

                 DFS(i);

         int k=;

         mem(vis,false);

         for(int i=vs.size()-;i >= ;--i)

             if(!vis[vs[i]])

                 RDFS(vs[i],++k);

         return k;

     }

 }_scc;

 int DFS(int u)///正向搜索比第 i 个数小的数

 {

     int ans=;

     vis[u]=true;

     for(int i=head[u];~i;i=G[i].next)

     {

         int v=G[i].to;

         if((i&) || vis[v])

             continue;

         ans += DFS(v);

     }

     return ans;

 }

 int RDFS(int u)///反向搜索比第 i 个数大的数

 {

     int ans=;

     vis[u]=true;

     for(int i=head[u];~i;i=G[i].next)

     {

         int v=G[i].to;

         if(!(i&) || vis[v])

             continue;

         ans += RDFS(v);

     }

     return ans;

 }

 bool isSat(int u)

 {

     mem(vis,false);

     int tot1=DFS(u)-;

     mem(vis,false);

     int tot2=RDFS(u)-;

     return abs(tot1-tot2) <= (n-tot1-tot2-) ? true:false;

 }

 char *Solve()

 {

     mem(s,'');

     s[n]='\0';

     int k=_scc.scc();///强连通分量分解判断是否含有环

     if(k < n)

         isCir=true;

     if(isCir)

         return s;

     for(int i=;i <= n;++i)

         if(isSat(i))///判断第 i 个数是否为median

             s[i-]='';

     return s;

 }

 void Init()

 {

     num=;

     mem(head,-);

     isCir=false;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     int test;

     scanf("%d",&test);

     while(test--)

     {

         scanf("%d%d",&n,&m);

         Init();

         for(int i=;i <= m;++i)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             if(u == v)

                 isCir=true;

             addEdge(u,v);///正向边

             addEdge(v,u);///反向边

         }

         printf("%s\n",Solve());

     }

     return ;

 }

凯少思路：

如果 tot1 ≤ n/2 && tot2 ≤ n/2 返回 true；

在返回结果的时候改成这句也可以，我的判断方法也对；

代码：

 #include <iostream>

 #include <vector>

 #include <cstring>

 #include <queue>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <stack>

 using namespace std;

 const int ss = ;

 int v1[ss];

 int v2[ss];

 int dfn[ss];

 int low[ss];

 int vis[ss];

 int son1[ss];

 int son2[ss];

 int pot[ss];

 vector < int >G[ss];

 vector < int >P[ss];

 stack < int >S;

 int scc, tim, n, m, t;

 void start()

 {

     memset(v1, , sizeof(v1));

     memset(v2, , sizeof(v2));

     memset(dfn, , sizeof(dfn));

     memset(vis, , sizeof(vis));

     memset(low, , sizeof(low));

     memset(pot, , sizeof(pot));

     memset(son1, , sizeof(son1));

     memset(son2, , sizeof(son2));

     for (int i = ; i <= n; i++)

     {

         G[i].clear();

         P[i].clear();

     }

     while (!S.empty())

         S.pop();

     scc = tim = n = m = ;

 }

 void tar(int u)

 {

     int v;

     low[u] = dfn[u] = ++tim;

     S.push(u);

     vis[u] = ;

     for (int i = ; i < G[u].size(); i++)

     {

         v = G[u][i];

         if (!dfn[v])

         {

             tar(v);

             if (low[u] > low[v])

                 low[u] = low[v];

         } else if (vis[v] && low[u] > dfn[v])

             low[u] = dfn[v];

     }

     if (low[u] == dfn[u])

     {

         scc++;

         do

         {

             v = S.top();

             S.pop();

             vis[v] = ;

         } while (v != u);

     }

 }

 int dfs1(int x)

 {

     v1[x] = ;

     for (int i = ; i < G[x].size(); i++)

     {

         if (!v1[G[x][i]])

             son1[x] += dfs1(G[x][i]);

     }

     return son1[x] + ;

 }

 int dfs2(int x)

 {

     v2[x] = ;

     for (int i = ; i < P[x].size(); i++)

     {

         if (!v2[P[x][i]])

             son2[x] += dfs2(P[x][i]);

     }

     return son2[x] + ;

 }

 void print(int x, int p)

 {

     for (int i = ; i <= n; i++)

     {

         if (i == p)

             printf("");

         else

             printf("");

     }

     printf("\n");

 }

 int main()

 {

     cin >> t;

     while (t--)

     {

         start();

         int ok = ;

         cin >> n >> m;

         for (int i = ; i <= m; i++)

         {

             int a, b;

             scanf("%d%d", &a, &b);

             if (a == b)

                 ok = ;

             G[a].push_back(b);

             P[b].push_back(a);

         }

         if (!ok)

         {

             print(n, );

         } else

         {

             for (int i = ; i <= n; i++)

                 if (!dfn[i])

                     tar(i);

             if (scc != n)

                 print(n, );

             else

             {

                 int point = ;

                 for (int i = ; i <= n; i++)

                 {

                     dfs1(i);

                     dfs2(i);

                     if ((son1[i] <= (n / )) && (son2[i] <= (n / )))

                         pot[i] = ;

                     memset(son1, , sizeof(son1));

                     memset(son2, , sizeof(son2));

                     memset(v1, , sizeof(v1));

                     memset(v2, , sizeof(v2));

                 }

                 for (int i = ; i <= n; i++)

                     cout << pot[i];

                 cout << "\n";

             }

         }

     }

     return ;

 }

因为 n 很小，所以对每个点跑两次DFS并不会超时；

但，如果 n 大了呢，那制定不能每个点跑两次DFS了，那该肿么办呢？

本蒟蒻还没想出来~~~~~~~~

据说，此题正解为求解两次拓扑序；

https://paste.ubuntu.com/p/xXxYdnDRBV/

巴特西

zoj 4124 "Median" （思维？假的图论？）

最新文章

热门文章