Minimizing Edges--Platinum_Minimizing Edges--Platinum题解|信奥算法练习题库-ACGO题库

登录

注册

题目详情题解（0）讨论（0）提交记录（0）

题解
法兰西玫瑰
94阅读
3回复
5点赞
题解
内存最优
zhouty
13阅读
0回复
1点赞
题解
#include<bits/stdc++.h> using namespace std; DEFINE LL LONG LONG DEFINE READ READ1<LL>() DEFINE TYPE TEMPLATE<TYPENAME T> Type T read1(){ T t=0;char k;bool vis=0; do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9'); while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar(); return vis?-t:t; } DEFINE FRE(K) FREOPEN(K".IN","R",STDIN);FREOPEN(K".OUT","W",STDOUT) struct B{ int x,y; B(int _x=0,int _y=0):x(_x),y(_y){} bool operator <(const B &t)const{return x+yt.x+t.y?y<t.y:x+y<t.x+t.y;} bool operator (const B &t)const{return xt.x&&yt.y;} }; map<int,int>U[100015],S[100015]; struct E{int u,t;}G[400005]; int f[100005],s,m,tot,dis[100005][2],q[200005]; bool r[200005];vector<B>tem; void add(int u,int v){ G[++tot].u=v;G[tot].t=f[u];f[u]=tot; G[++tot].u=u;G[tot].t=f[v];f[v]=tot; } int main(){q[0]=1;r[0]=0; for(int T=read;T--;){ s=read,m=read;tot=0; memset(f,0,s+1<<2); memset(dis,-1,s+1<<3); for(int i=1;i<=m;++i) add(read,read); for(int i=0;i<=s+5;++i)S[i].clear(),U[i].clear(); dis[1][0]=0; for(int i=0,j=1;i!=j;++i){ int n=q[i]; for(int x=f[n];x;x=G[x].t) if(!~dis[G[x].u][!r[i]]){ r[j]=!r[i];q[j]=G[x].u;++j; dis[G[x].u][!r[i]]=dis[n][r[i]]+1; } }int ans=0; if(!~dis[1][1])ans=s-1; else if(dis[1][1]1)ans=s; else{tem.clear(); for(int i=2;i<=s;++i){ int x=dis[i][0],y=dis[i][1]; if(y>x)swap(x,y); ++S[x][y];tem.push_back(B(x,y)); }S[dis[1][1]][0]=1; sort(tem.begin(),tem.end()); B v(114514,-1); for(int i=0;i<tem.size();++i){ if(vtem[i]) continue; v=tem[i]; int cnt=S[v.x][v.y],h=S[v.x-1][v.y-1],p=U[v.x+1][v.y-1]; if(!h)ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=cnt:cnt+1>>1); else if(!p)ans+=cnt; else ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=min(cnt,p):min(cnt,p)+1>>1); } } printf("%d\n",ans); } return 0; }
Alex
17阅读
0回复
0点赞
题解
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; typedef pair<int,int> PII; inline int readint(){ int a = 0; char c = getchar(), f = 1; for(; c<'0'||c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c&&c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f; } const int MaxN = 100005; const int MaxM = 200005; namespace queue{ int q[MaxN<<1]; typedef int* iterator; iterator begin(){ return q; } } namespace Graph{ struct Edge{ int to, nxt; Edge(){} Edge(int T,int N){ to = T, nxt = N; } }; Edge e[MaxM<<2]; int cntEdge, head[MaxN<<1]; void addEdge(int a,int b){ e[cntEdge] = Edge(b,head[a]); head[a] = cntEdge ++; e[cntEdge] = Edge(a,head[b]); head[b] = cntEdge ++; } int dep[MaxN<<1]; void input(int n,int m){ for(int i=1; i<=2*n; ++i) dep[i] = head[i] = -1; cntEdge = 0; // several cases for(int i=1,a,b; i<=m; ++i){ a = readint(), b = readint(); addEdge(a,b+n), addEdge(a+n,b); } } void scan(){ queueiterator fro = queuebegin(); queueiterator bac = queuebegin(); *(bac ++) = 1; dep[1] = 0; for(; fro!=bac; ++fro) for(int i=head[*fro]; ~i; i=e[i].nxt) if(dep[e[i].to] == -1){ dep[e[i].to] = dep[*fro]+1; *(bac ++) = e[i].to; } } } int n, m; void input(){ n = readint(), m = readint(); Graphinput(n,m), Graphscan(); } int ans; DEFINE DDQ VECTOR<PII>::ITERATOR int eliminateChain(const DDQ &bg,const DDQ &ed){ int used = 0; for(DDQ i=ed; i!=bg; --i){ used = min(i->second-used,(i-1)->second); ans += used; } return bg->second-used; } UNDEF DDQ bool vis[MaxN<<1]; vector<int> tree[MaxN<<1]; vector<PII> len_cnt; vector<int> trash; int getOnion(){ using Graph::dep; int tot = 0; for(int i=1; i<=n; ++i){ int l = dep[i], r = dep[i+n]; if(l > r) swap(l,r); if(l != -1) tree[l+r].push_back(r-l+1); tot += (l != -1) + (r != -1); } ans = 0; trash.clear(); memset(vis+1,0,n<<1); for(int i=1; i<=2*n; i+=2){ len_cnt.clear(); vector<int> &v = tree[i]; sort(v.begin(),v.end()); int len = v.size(); for(int p=0,j=p; p!=len; p=j){ while(j != len && v[j] == v[p]) ++ j; len_cnt.push_back(make_pair(v[p],j-p)); len_cnt.push_back(make_pair(v[p],j-p)); } len = len_cnt.size(); for(int p=0,j=p; p!=len; p=++j){ while(j+1 != len) if(j&1){ if(len_cnt[j+1].first == len_cnt[j].first+2) ++ j; else break; } else{ if(vis[len_cnt[j].first]) ++ j; else break; } int rest = eliminateChain(len_cnt.begin()+p,len_cnt.begin()+j); if(!p && len_cnt[0].first == 2) ans += (rest>>1); } while(!trash.empty()){ vis[trash.back()] = false; trash.pop_back(); } while(!len_cnt.empty()){ trash.push_back(len_cnt.back().first); len_cnt.pop_back(); vis[trash.back()] = true; } } return tot-1-ans; } void solve(){ for(int i=1; i<=2*n; i+=2) tree[i].clear(); printf("%d\n",getOnion()); } int main(){ for(int T=readint(); T; --T) input(), solve(); return 0; }
吴卡 ━━╋══════➢
6阅读
0回复
0点赞
题解
#include<bits/stdc++.h> using namespace std; DEFINE LL LONG LONG DEFINE READ READ1<LL>() DEFINE TYPE TEMPLATE<TYPENAME T> Type T read1(){ T t=0;char k;bool vis=0; do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9'); while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar(); return vis?-t:t; } DEFINE FRE(K) FREOPEN(K".IN","R",STDIN);FREOPEN(K".OUT","W",STDOUT) struct B{ int x,y; B(int _x=0,int _y=0):x(_x),y(_y){} bool operator <(const B &t)const{return x+yt.x+t.y?y<t.y:x+y<t.x+t.y;} bool operator (const B &t)const{return xt.x&&yt.y;} }; map<int,int>U[100015],S[100015]; struct E{int u,t;}G[400005]; int f[100005],s,m,tot,dis[100005][2],q[200005]; bool r[200005];vector<B>tem; void add(int u,int v){ G[++tot].u=v;G[tot].t=f[u];f[u]=tot; G[++tot].u=u;G[tot].t=f[v];f[v]=tot; } int main(){q[0]=1;r[0]=0; for(int T=read;T--;){ s=read,m=read;tot=0; memset(f,0,s+1<<2); memset(dis,-1,s+1<<3); for(int i=1;i<=m;++i) add(read,read); for(int i=0;i<=s+5;++i)S[i].clear(),U[i].clear(); dis[1][0]=0; for(int i=0,j=1;i!=j;++i){ int n=q[i]; for(int x=f[n];x;x=G[x].t) if(!~dis[G[x].u][!r[i]]){ r[j]=!r[i];q[j]=G[x].u;++j; dis[G[x].u][!r[i]]=dis[n][r[i]]+1; } }int ans=0; if(!~dis[1][1])ans=s-1; else if(dis[1][1]1)ans=s; else{tem.clear(); for(int i=2;i<=s;++i){ int x=dis[i][0],y=dis[i][1]; if(y>x)swap(x,y); ++S[x][y];tem.push_back(B(x,y)); }S[dis[1][1]][0]=1; sort(tem.begin(),tem.end()); B v(114514,-1); for(int i=0;i<tem.size();++i){ if(vtem[i]) continue; v=tem[i]; int cnt=S[v.x][v.y],h=S[v.x-1][v.y-1],p=U[v.x+1][v.y-1]; if(!h)ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=cnt:cnt+1>>1); else if(!p)ans+=cnt; else ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=min(cnt,p):min(cnt,p)+1>>1); } } printf("%d\n",ans); } return 0; }

2阅读
0回复
0点赞
题解
#include<bits/stdc++.h> using namespace std; DEFINE LL LONG LONG DEFINE READ READ1<LL>() DEFINE TYPE TEMPLATE<TYPENAME T> Type T read1(){ T t=0;char k;bool vis=0; do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9'); while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar(); return vis?-t:t; } DEFINE FRE(K) FREOPEN(K".IN","R",STDIN);FREOPEN(K".OUT","W",STDOUT) struct B{ int x,y; B(int _x=0,int _y=0):x(_x),y(_y){} bool operator <(const B &t)const{return x+yt.x+t.y?y<t.y:x+y<t.x+t.y;} bool operator (const B &t)const{return xt.x&&yt.y;} }; map<int,int>U[100015],S[100015]; struct E{int u,t;}G[400005]; int f[100005],s,m,tot,dis[100005][2],q[200005]; bool r[200005];vector<B>tem; void add(int u,int v){ G[++tot].u=v;G[tot].t=f[u];f[u]=tot; G[++tot].u=u;G[tot].t=f[v];f[v]=tot; } int main(){q[0]=1;r[0]=0; for(int T=read;T--;){ s=read,m=read;tot=0; memset(f,0,s+1<<2); memset(dis,-1,s+1<<3); for(int i=1;i<=m;++i) add(read,read); for(int i=0;i<=s+5;++i)S[i].clear(),U[i].clear(); dis[1][0]=0; for(int i=0,j=1;i!=j;++i){ int n=q[i]; for(int x=f[n];x;x=G[x].t) if(!~dis[G[x].u][!r[i]]){ r[j]=!r[i];q[j]=G[x].u;++j; dis[G[x].u][!r[i]]=dis[n][r[i]]+1; } }int ans=0; if(!~dis[1][1])ans=s-1; else if(dis[1][1]1)ans=s; else{tem.clear(); for(int i=2;i<=s;++i){ int x=dis[i][0],y=dis[i][1]; if(y>x)swap(x,y); ++S[x][y];tem.push_back(B(x,y)); }S[dis[1][1]][0]=1; sort(tem.begin(),tem.end()); B v(114514,-1); for(int i=0;i<tem.size();++i){ if(vtem[i]) continue; v=tem[i]; int cnt=S[v.x][v.y],h=S[v.x-1][v.y-1],p=U[v.x+1][v.y-1]; if(!h)ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=cnt:cnt+1>>1); else if(!p)ans+=cnt; else ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=min(cnt,p):min(cnt,p)+1>>1); } } printf("%d\n",ans); } return 0; }
复仇者_黑客_ZDZL
1阅读
0回复
0点赞
6666
耐高总冠军张文杰
0阅读
0回复
0点赞