Median ZOJ - 4124 （dfs+拓扑判环）
题目链接：
Median
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：给你n个数，m条对应关系，每一条对应关系给你的是i和j，代表a[i]>a[j]。然后你可以给这些点赋值，但是大小关系必须是按照给你的来，如果没有给定那就可以随便赋值。然后问你是否存在这样的点，满足有一半的数大于当前这个数，并且有一半的数小于当前的这个数。这个点对于的坐标输出1，否则输出0.
具体思路：首先拓扑判环，然后判断每一个点大于他的有多少，小于它的有多少，然后判断是不是个数都小于等于(n-1)/2(n保证为奇数)，如果当前的点都满足的话，那么这个点一定是符合情况的。他给你的图有可能是不完全的，也就是说对于那些没有给定关系的点，我们是可以随便赋值的，所以只需要判断当前图中小于它的是不是小于(n-1)/2个就好了。
用spfa判环的时候，要先使得整个图都是联通的，所以我们可以新加一个超级源点使得整个图变成联通的，权值为1
在dfs的时候，注意子节点的计算方式，当构成的图为菱形的时候，最后一个点极有可能计算多次。
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 const int N = 100+10; 7 vector<int>tr[N]; 8 vector<int>fa[N]; 9 int ans[N]; 10 int n; 11 int in[N]; 12 int vis[N]; 13 int down[N],up[N]; 14 void init() 15 { 16 for(int i=0; i<=n; i++) 17 { 18 ans[i]=0; 19 tr[i].clear(); 20 fa[i].clear(); 21 in[i]=0; 22 } 23 } 24 void print() 25 { 26 for(int i=1; i<=n; i++) 27 { 28 printf("0"); 29 } 30 printf("\n"); 31 } 32 bool tuopu() 33 { 34 queue<int>q; 35 while(!q.empty()) 36 q.pop(); 37 for(int i=1; i<=n; i++) 38 { 39 if(!in[i]) 40 q.push(i); 41 } 42 while(!q.empty()) 43 { 44 int top=q.front(); 45 q.pop(); 46 vis[top]=1; 47 for(int i=0; i<tr[top].size(); i++) 48 { 49 int to=tr[top][i]; 50 if(--in[to]==0) 51 q.push(to); 52 } 53 } 54 for(int i=1; i<=n; i++) 55 { 56 if(!vis[i]) 57 return false; 58 } 59 return true; 60 } 61 int cnt; 62 void dfs1(int u,int rt) 63 { 64 vis[u]=1; 65 for(int i=0; i<tr[u].size(); i++) 66 { 67 int to=tr[u][i]; 68 if(!vis[to]) 69 { 70 cnt++; 71 dfs1(to,u); 72 } 73 } 74 } 75 void dfs2(int u,int rt) 76 { 77 vis[u]=1; 78 for(int i=0; i<fa[u].size(); i++) 79 { 80 int to=fa[u][i]; 81 if(!vis[to]) 82 { 83 cnt++; 84 dfs2(to,u); 85 } 86 } 87 } 88 int main() 89 { 90 int T; 91 scanf("%d",&T); 92 while(T--) 93 { 94 int m; 95 scanf("%d %d",&n,&m); 96 init(); 97 int st,ed; 98 for(int i=1; i<=m; i++) 99 { 100 scanf("%d %d",&st,&ed); 101 tr[st].push_back(ed); /// 正向图 102 fa[ed].push_back(st); /// 反向图 103 in[ed]++; 104 } 105 memset(vis,0,sizeof(vis)); 106 if(!tuopu())/// 判环 107 { 108 print(); 109 continue; 110 } 111 for(int i=1; i<=n; i++) 112 { 113 cnt=0; 114 memset(vis,0,sizeof(vis)); 115 dfs1(i,-1);/// 判断有多少个大于当前节点 116 down[i]=cnt; 117 } 118 for(int i=1; i<=n; i++) 119 { 120 cnt=0; 121 memset(vis,0,sizeof(vis)); 122 dfs2(i,-1);/// 判断有多少个小于当前节点 123 up[i]=cnt; 124 } 125 for(int i=1; i<=n; i++) 126 { 127 if(down[i]<=(n-1)/2&&up[i]<=(n-1)/2) 128 { 129 ans[i]=1; 130 } 131 } 132 for(int i=1; i<=n; i++) 133 { 134 printf("%d",ans[i]); 135 } 136 printf("\n"); 137 } 138 return 0; 139 } 140 /* 141 2 142 9 8 143 1 3 144 1 4 145 1 5 146 4 2 147 6 1 148 7 1 149 8 1 150 9 6 151 */
拓扑判环
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 const int N = 100+10; 7 vector<int>tr[N]; 8 vector<int>fa[N]; 9 vector<pair<int,int> >sp[N]; 10 int ans[N]; 11 int n; 12 int in[N]; 13 int vis[N]; 14 int down[N],up[N]; 15 int dis[N]; 16 void init() 17 { 18 for(int i=0; i<=n; i++) 19 { 20 ans[i]=0; 21 tr[i].clear(); 22 fa[i].clear(); 23 sp[i].clear(); 24 in[i]=0; 25 dis[i]=0; 26 } 27 } 28 void print() 29 { 30 for(int i=1; i<=n; i++) 31 { 32 printf("0"); 33 } 34 printf("\n"); 35 } 36 bool spfa() 37 { 38 queue<int>q; 39 while(!q.empty()) 40 q.pop(); 41 q.push(0); 42 while(!q.empty()) 43 { 44 int top=q.front(); 45 q.pop(); 46 if(++vis[top]>n) 47 return false; 48 for(int i=0; i<sp[top].size(); i++) 49 { 50 int to=sp[top][i].first; 51 if(dis[to]<dis[top]+sp[top][i].second) 52 { 53 dis[to]=dis[top]+sp[top][i].second; 54 q.push(to); 55 } 56 } 57 } 58 return true; 59 } 60 int cnt; 61 void dfs1(int u,int rt) 62 { 63 vis[u]=1; 64 for(int i=0; i<tr[u].size(); i++) 65 { 66 int to=tr[u][i]; 67 if(!vis[to]) 68 { 69 cnt++; 70 dfs1(to,u); 71 } 72 } 73 } 74 void dfs2(int u,int rt) 75 { 76 vis[u]=1; 77 for(int i=0; i<fa[u].size(); i++) 78 { 79 int to=fa[u][i]; 80 if(!vis[to]) 81 { 82 cnt++; 83 dfs2(to,u); 84 } 85 } 86 } 87 int main() 88 { 89 int T; 90 scanf("%d",&T); 91 while(T--) 92 { 93 int m; 94 scanf("%d %d",&n,&m); 95 init(); 96 int st,ed; 97 for(int i=1; i<=m; i++) 98 { 99 scanf("%d %d",&st,&ed); 100 tr[st].push_back(ed); /// 正向图 101 fa[ed].push_back(st); /// 反向图 102 sp[st].push_back(make_pair(ed,1)); 103 in[ed]++; 104 } 105 for(int i=1;i<=n;i++){ 106 sp[0].push_back(make_pair(i,1)); 107 } 108 memset(vis,0,sizeof(vis)); 109 if(!spfa())/// 判环 110 { 111 // cout<<1<<endl; 112 print(); 113 continue; 114 } 115 for(int i=1; i<=n; i++) 116 { 117 cnt=0; 118 memset(vis,0,sizeof(vis)); 119 dfs1(i,-1);/// 判断有多少个大于当前节点 120 down[i]=cnt; 121 } 122 for(int i=1; i<=n; i++) 123 { 124 cnt=0; 125 memset(vis,0,sizeof(vis)); 126 dfs2(i,-1);/// 判断有多少个小于当前节点 127 up[i]=cnt; 128 } 129 for(int i=1; i<=n; i++) 130 { 131 if(down[i]<=(n-1)/2&&up[i]<=(n-1)/2) 132 { 133 ans[i]=1; 134 } 135 } 136 for(int i=1; i<=n; i++) 137 { 138 printf("%d",ans[i]); 139 } 140 printf("\n"); 141 } 142 return 0; 143 } 144 /* 145 2 146 9 8 147 1 3 148 1 4 149 1 5 150 4 2 151 6 1 152 7 1 153 8 1 154 9 6 155 */
spfa判环
更多精彩
