图论错题集1

Problem - 1651D - Codeforces

Problem - E - Codeforces

题意：给一颗无向无根树，让你给每个点分配一个点权，使得去掉任意一个结点后，剩余的每个连通块的点权值和相等。

思路：构造题，首先对图进行黑白染色，让所有白点权值为其度数，黑点为其度数的相反数。首先这样构造可以保证整棵树所有的点权值和为0，当我删除任意一个点后，我把我删除的这个点看作根节点的话，如果它的点权为正，则剩下所有子树的权值和都是-1，如果它的点权为负，则剩下所有子树的权值和都是1，因为点的权值右度数决定，所以相当于每条边带来的贡献是1。

#include 
using namespace std;
#define visit _visit
#define next _next
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ll long long
#define pint pairconst int mod = 998244353;
const int maxn = 200001;
const int INF = 0x3f3f3f3f;void read(int &x){int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;
}
ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll inv(ll x) {return quick_pow(x, mod-2);}
//----------------------------------------------------------------------------------------------------------------------//
struct node{int ne,to;
};
node edge[maxn<<1];
int head[maxn];
int cnt=0;
void addedge(int a,int b){edge[cnt].to=b;edge[cnt].ne=head[a];head[a]=cnt++;
}
int color[maxn];
void dfs(int x,int fa,int c){color[x]=c%2;for(int i=head[x];i!=-1;i=edge[i].ne){int son=edge[i].to;if(fa==son){continue;}dfs(son,x,c+1);}
}
int du[maxn];
void solve(){int n;cin>>n;cnt=0;for(int i=0;i<=n*2;i++){head[i]=-1;}for(int i=1;i<=n;i++){du[i]=0;}for(int i=1;i>a>>b;addedge(a,b);addedge(b,a);du[a]++;du[b]++;}dfs(1,0,0);for(int i=1;i<=n;i++){if(color[i]==1){du[i]*=-1;}cout<>t;while(t--){solve();}return 0;
}

https://ac.nowcoder.com/acm/problem/51269

题意：一张有向图，求：

1-最少要从几个点开始能遍历完所有的点

2-最少要添加几条边能让所有的点都在一个强连通分量里

思路：对问题1，我们只需要缩点后找入度为0的点的数量即可。

对问题2，我们观察缩点之后的新图，这显然是一个有向无环图，而要使得所有的点都在一个强连通分量里，最节省的方法肯定是让他们组成一个环，而在一个环中，每个点的入度和出度都不为0，因此我们需要处理的点一定就是那些入度为0或者出度为0的点，所以我们把每个出度为0的点连向一个入度为0的点即可，只要一张图里既没有入度为0的点也没有出度为0的点，那么这张图一定是由若干环组成，而想要把若干个小环组成一个大环，我们只要错位连边即可，即上一个环中取下一条边连到下一个环上，后面同理即可。所以答案就是max(入度为0的点的个数，出度为0的点的个数)。

 #include using namespace std;#define visit _visit#define next _next#define pb push_back#define fi first#define se second#define endl '\n'#define fast ios::sync_with_stdio(0), cin.tie(0)#define int long long#define ll long long#define pint pair​const int mod = 998244353;const int maxn = 100001;const int maxm = 5000001;const int INF = 0x3f3f3f3f;​void read(int &x){int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;}ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}ll inv(ll x) {return quick_pow(x, mod-2);}//----------------------------------------------------------------------------------------------------------------------//struct node{int ne,to;};node edge[maxm];int head[maxn];int cnt=0;void addedge(int a,int b){edge[cnt].to=b;edge[cnt].ne=head[a];head[a]=cnt++;}int dfn[maxn],vis[maxn],color[maxn],low[maxn],dn,c;stacks;void tarjan(int x){dfn[x]=low[x]=++dn;s.push(x);vis[x]=1;for(int i=head[x];i!=-1;i=edge[i].ne){int son=edge[i].to;if(dfn[son]==0){tarjan(son);low[x]=min(low[x],low[son]);}else if(vis[son]==1){low[x]=min(low[x],dfn[son]);}}if(low[x]==dfn[x]){c++;while(1){int t=s.top();s.pop();vis[t]=0;color[t]=c;if(t==x){break;}}}}int ru[maxn],chu[maxn];void solve(){memset(head,-1,sizeof(head));int n;read(n);for(int i=1;i<=n;i++){int a=1;while(a!=0){read(a);if(a==0){break;}addedge(i,a);}}for(int i=1;i<=n;i++){if(dfn[i]==0){tarjan(i);}}for(int i=1;i<=n;i++){for(int j=head[i];j!=-1;j=edge[j].ne){int son=edge[j].to;if(color[son]==color[i]){continue;}else{ru[color[son]]++;chu[color[i]]++;}}}​int cnt1=0,cnt2=0;for(int i=1;i<=c;i++){cnt1+=ru[i]==0;cnt2+=chu[i]==0;}if(c==1){cout<<1<<" "<<0<>t;while(t--){solve();}return 0;}

Problem - 1245D - Codeforces

题意：给定一些坐标系上的点，我要把所有的点都通上电，一个点要么自己画ci的价钱通上电，要么花dis(i,j)*(k[i]+k[j])的价钱和另一个通了电的点相连，求把所有的点都通上电的最小花费

思路：平台点+最小数生成树，首先我们假设我们只给一个点通电其余全部链接的话，很容易发现这是个最小生成树，再考虑只给两个点通电的情况，这时候就相当于两个子最小生成树，那么怎么把他们连起来考虑呢？我们建一个平台点向所有结点连边，边权为ci，那么对于每个点来说它的所有的可能状态都能用边表示出来了：与其他n-1个点中的某个相连、自己通电，然后我们在这张新图上跑最小生成树即可。

太刁了，我超，我tm在那贪心了一年根本没想到最小生成树。

 #include using namespace std;#define visit _visit#define next _next#define pb push_back#define fi first#define se second#define endl '\n'#define fast ios::sync_with_stdio(0), cin.tie(0)#define int long long#define ll long long#define pint pair​const int mod = 998244353;const int maxn = 2010;const int INF = 0x3f3f3f3f;​void read(int &x){int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;}ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}ll inv(ll x) {return quick_pow(x, mod-2);}//----------------------------------------------------------------------------------------------------------------------//struct node{int st,to,val;};node edge[maxn*maxn+maxn];int cnt=0;void addedge(int a,int b,int val){edge[cnt].st=a;edge[cnt].to=b;edge[cnt].val=val;cnt++;}bool com(node a,node b){return a.val>n;for(int i=0;i<=n;i++){fa[i]=i;}for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}for(int i=1;i<=n;i++){cin>>c[i];addedge(0,i,c[i]);}for(int i=1;i<=n;i++){cin>>k[i];}​for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){addedge(i,j,calc(i,j));}}sort(edge,edge+cnt,com);// for(int i=0;ians2;vectorans3;for(int i=0;i=cnt){break;}int s=edge[pos].st;int t=edge[pos].to;if(find(s)==find(t)){pos++;continue;}else{join(s,t);ans1+=edge[pos].val;if(s==0){ans2.pb(t);}else if(t==0){ans2.pb(s);}else{ans3.pb({s,t});}pos++;break;}}}cout<>t;while(t--){solve();}return 0;}

Problem - 832D - Codeforces

题意：一张无向图，给定三个点，选择其中任意一个点为起点，其余两个点为终点，问你选哪个点作为起点能使得这两条路径的重合的部分最长。

思路：很容易想到和最近公共祖先有关系，但是也不知道我是不是脑子抽了，居然没推出公式：

 太废物了，呜呜呜

 #include using namespace std;#define visit _visit#define next _next#define pb push_back#define fi first#define se second#define endl '\n'#define fast ios::sync_with_stdio(0), cin.tie(0)#define int long long#define ll long long#define pint pair​const int mod = 998244353;const int maxn = 200001;const int INF = 0x3f3f3f3f;​void read(int &x){int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;}ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}ll inv(ll x) {return quick_pow(x, mod-2);}//----------------------------------------------------------------------------------------------------------------------//struct node{int ne,to;};node edge[maxn<<1];int head[maxn];int e=0;void addedge(int a,int b){edge[e].to=b;edge[e].ne=head[a];head[a]=e++;}int cnt;int dis[maxn];int dfn[maxn<<1];int mp[maxn];int fi[maxn];int num=0;void dfs(int x,int fa){num++;int tem=num;dfn[++cnt]=num;mp[num]=x;fi[x]=cnt;if(x==1){dis[x]=0;}else{dis[x]=dis[fa]+1;}for(int i=head[x];i!=-1;i=edge[i].ne){int son=edge[i].to;if(son==fa){continue;}dfs(son,x);dfn[++cnt]=tem;}}int st[21][maxn<<1];void rmq_st(){for(int i=1;i<=cnt;i++){st[0][i]=dfn[i];}int k=(int)(log(cnt*1.0)/log(2.0));for(int i=1;i<=k+1;i++){int len=(1<fi[b]){swap(a,b);}return mp[rmq_find(fi[a],fi[b])];}int calc(int a,int b){int fa=LCA(a,b);return dis[a]+dis[b]-2*dis[fa];}int fun(int a,int b,int c){return (calc(a,b)+calc(a,c)-calc(c,b))/2+1;}void solve(){memset(head,-1,sizeof(head));int n,q;cin>>n>>q;for(int i=2;i<=n;i++){int f;cin>>f;addedge(i,f);addedge(f,i);}dfs(1,-1);rmq_st();while(q--){int a,b,c;cin>>a>>b>>c;​int ans=0;ans=max({fun(a,b,c),fun(b,a,c),fun(c,a,b)});cout<>t;while(t--){solve();}return 0;}

https://loj.ac/p/136

最小瓶颈路板子，最小瓶颈路就是两点之间路径上最大的那条边权的最小值。用到的知识点是kruscal重构树+lca，kruscal重构树可以将点权转换成边权，并且使得新图是一个大根堆，所有的原图的结点在新图上都是叶子节点。

 #include using namespace std;#define visit _visit#define next _next#define pb push_back#define fi first#define se second#define endl '\n'#define fast ios::sync_with_stdio(0), cin.tie(0)#define int long long#define ll long long#define pint pair​const int mod = 1e9+7;const int maxn = 200001;const int INF = 0x3f3f3f3f;​void read(int &x){int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;}ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}ll inv(ll x) {return quick_pow(x, mod-2);}//----------------------------------------------------------------------------------------------------------------------//struct e{int a,b,val;};e es[maxn];struct node{int ne,to;};node edge[maxn<<1];int head[maxn];int pnum;int cnt=0;void addedge(int a,int b){edge[cnt].to=b;edge[cnt].ne=head[a];head[a]=cnt++;}int val[maxn];int fa[maxn];int find(int x){if(fa[x]==x){return x;}return fa[x]=find(fa[x]);}bool com(e a,e b){return a.valfi[b]){swap(a,b);}return mp[rmq_find(fi[a],fi[b])];}int A,B,C,P;inline int rnd(){return A=(A*B+C)%P;}​void solve(){memset(head,-1,sizeof(head));int n,m,k;cin>>n>>m;for(int i=1;i<=n*2;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>es[i].a>>es[i].b>>es[i].val;}sort(es+1,es+1+m,com);pnum=n;int tes=1;for(int i=1;i<=m;i++){int a=es[i].a;int b=es[i].b;int fa1=find(a);int fa2=find(b);if(fa1==fa2){continue;}else{tes++;pnum++;fa[fa1]=pnum;fa[fa2]=pnum;addedge(fa1,pnum);addedge(pnum,fa1);addedge(fa2,pnum);addedge(pnum,fa2);val[pnum]=es[i].val;}if(tes==n){break;}}dfs(find(1),-1);rmq_st();cin>>k; cin>>A>>B>>C>>P;int ans=0;for(int i=1;i<=k;i++){int a=rnd()%n+1;int b=rnd()%n+1;int res=val[LCA(a,b)];ans+=res;ans%=mod;}cout<>t;while(t--){solve();}return 0;}

typora写的多了后就开始卡了，就先发一部分了。。。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！