图论专题总结

T1菜肴制作：拓扑排序+大根堆

卡了好一会儿才过掉。正序拓扑的话贪心策略会出错。

保证先输出小的，倒序拓扑保证先搞大的。然后插到大根堆里。

每次取出最大的（堆顶）进行拓扑扩展。pop出来的直接扔进栈里。

多判有点恶心。记得清空（我就因为tot没清空，样例第三组单测正确，多测就错。。）

还有一个特殊判断：栈内元素个数与本身元素个数是否相符。

不相符就是剩下了环搞不出来，就行了。

#include
#include
#include
#include
#include
#include
#define rint register int
using namespace std;
int T,n,m,a,b,tot,first[100003];
int du[100003];
struct node{int u,v,nxt;
};
bool pan=0,vis[100003];
inline void add(int uu,int vv,node edge[])
{++tot;edge[tot].u=uu;edge[tot].v=vv;edge[tot].nxt=first[uu];first[uu]=tot;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d %d",&n,&m);memset(vis,0,sizeof(vis));memset(du,0,sizeof(du));memset(first,0,sizeof(first));tot=0;priority_queue <int> q;stack <int> s;node edge[100003];for(rint i=1;i<=m;++i){scanf("%d %d",&a,&b);add(b,a,edge);du[a]++;}for(rint i=1;i<=n;++i){if(!du[i])q.push(i);vis[i]=1;}if(q.empty()){cout<<"Impossible!"<continue;}while(!q.empty()){int xx=q.top();s.push(xx);q.pop();
//            cout<pan=0;for(rint i=first[xx];i;i=edge[i].nxt){int yy=edge[i].v;du[yy]--;if(!du[yy]){pan=1;q.push(yy);
//                    cout<<"yy"<vis[yy]=1;}}
//            if(pan==0&&q.empty()){cout<<"Impossible!"<
        }
//        if(pan==0)continue;if(s.size()!=n){cout<<"Impossible!"<continue;}while(!s.empty()){cout<' ';s.pop();}cout<<endl;}
}

View Code

T2矩阵游戏：二分图

锝瑟一把这题全hzoj我是第一个A掉的

二分图，一开始还真没想起来。查bzoj上这道题的时候撇了一眼看到了二分图三个字。

好的。（不要脸）但是真的忘了啊QAQ只好翻出ftp里尘封多年的二分图ppt。

手码了一遍匈牙利感觉还不错。

挺基础，行列分别建点，黑格建边，跑一边匈牙利，用黑格去匹配行和列。

然而没认真看题，人家让输出“Yes”或“No”，我输出“YES”“NO”完美w0。。。

加了一堆卡常特盘，148毫算是挺快的了吧？（wtf 102ms！收小的一拜）

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=205;
int a[N][N];
int vis[N],matx[N],maty[N];
int tot;
int n;
int hun(int x)
{for(int i=1;i<=n;i++){//int y=to[i];if(!vis[i]&&a[x][i]){vis[i]=1;if(maty[i]==-1||hun(maty[i])){maty[i]=x;matx[x]=i;return 1;}}}return 0;
}
int main(){int T;scanf("%d",&T);while(T--){tot=0;memset(maty,-1,sizeof(maty));memset(matx,-1,sizeof(matx));scanf("%d",&n);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(hun(i)) ans++;}//cout<if(ans!=n){printf("No\n");}else puts("Yes\n");}
}

View Code

T3约会 ：基环树

为什么基环树的题目都这么恶心还是我太弱鸡了？

我可能卡了一年。自己想出来的代码5.0k，198行……我真的没勇气调下去了。

记录了一大堆东西。判断的语句写了一堆。。真的是堆QAQ。

#include
#include
#include
#include
#include
#include
#define rint register int
const int L=1<<20|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
using namespace std;
int n,m,head[500005],tot,fat[500005];
int dex,cnt,t,bar[500005],bl[500005],ac[500005];
int d[500005],f[500005][20],l_a[500005],l_b[500005];
vector<int>dell[500005];queue<int>q;
struct node{int to,nxt;}edge[500005];
int read()
{rint a=0,b=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}while(ch>='0'&&ch<='9'){a=a*10+ch-'0';ch=getchar();}return a*b;
}
void add(rint x,rint y)
{edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;
}
int find(rint x)
{if(fat[x]==x) return x;return fat[x]=find(fat[x]);
}
void get_dell(rint x,rint dex)
{bar[x]=dex;for(rint i=head[x];i;i=edge[i].nxt){rint y=edge[i].to;if(bar[y]==dex){++cnt;while(y!=x){dell[cnt].push_back(x);x=ac[x];}dell[cnt].push_back(y);}else ac[y]=x,get_dell(y,dex);}        
}
void bfs(rint x,rint tp)
{    d[x]=1,bl[x]=tp;q.push(x);while(!q.empty()){rint x=q.front();q.pop();for(rint i=head[x];i;i=edge[i].nxt){rint y=edge[i].to;if(!bar[y]&&!d[y]){bl[y]=tp;d[y]=d[x]+1;q.push(y);f[y][0]=x;for(rint j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1];}}}
}
int Lca(rint x,rint y)
{if(d[x]>d[y]) swap(x,y);for(rint i=t;i>=0;i--)if(d[f[y][i]]>=d[x]) y=f[y][i];if(x==y) return x;for(rint i=t;i>=0;i--){if(f[y][i]^f[x][i]){y=f[y][i];x=f[x][i];}}return f[x][0];
}
void solve()
{for(rint i=1;i<=n;i++)if(!bar[i]) get_dell(i,++dex);memset(bar,0,sizeof(bar));for(rint i=1;i<=cnt;i++)for(rint j=0;j)bar[dell[i][j]]=1,l_a[dell[i][j]]=j,l_b[dell[i][j]]=i;for(rint i=1;i<=cnt;i++)for(rint j=0;j)bfs(dell[i][j],dell[i][j]);
}
int main()
{n=read(),m=read();t=log2(n)+1;for(rint i=1;i<=n;i++) fat[i]=i;for(rint i=1,x;i<=n;i++){x=read();add(x,i);fat[find(i)]=find(x);}solve();for(rint i=1,x,y;i<=m;i++){x=read(),y=read();if(find(x)!=find(y)) printf("-1 -1\n");else if(bl[x]==bl[y]){rint lca=Lca(x,y);rint ll=d[x]-d[lca],rr=d[y]-d[lca]; printf("%d %d\n",ll,rr);}else {rint ll=abs(l_a[bl[x]]-l_a[bl[y]]),rr=dell[l_b[bl[x]]].size()-ll;rint edge=d[x]-d[bl[x]],r=d[y]-d[bl[y]];rint ans1,ans2,ans3,ans4;if(l_a[bl[x]]rr;else ans1=edge+rr,ans2=r,ans3=edge,ans4=r+ll;if(max(ans1,ans2)"%d %d\n",ans1,ans2);else if(max(ans1,ans2)>max(ans3,ans4)) printf("%d %d\n",ans3,ans4);else{if(min(ans1,ans2)"%d %d\n",ans1,ans2);else if(min(ans1,ans2)>min(ans3,ans4)) printf("%d %d\n",ans3,ans4);else printf("%d %d\n",max(ans1,ans2),min(ans1,ans2));}}}return 0;
}

View Code

：最小生成树+二分答案

被天皇忽悠说这道题贼恶心，去看题解（推锅推锅）然后1A掉不想说话。

不是特别好想。不过填了一种最小生成树题目的做题方法：通过改变边权来改变最小生成树的构成。

黑白边，要求need条白边。一开始sb的想成了树里只有白边。

显然还有n-1-need条黑边 /糊脸（n是节点数目）顺嘴吐槽：BZOJ上直接跑最小生成树都能过……

二分给白边加上边权，跑最小生成树，看是否符合need条白边。

直接暴力累计就好了没必要开优化（懒）还有人直接爆搜不二分都A了……

建议打二分咕咕咕～

#include
#include
#include
#include
#include
#include
#include
#define rint register int
using namespace std;
int n,m,need,l,r,cnt,tot,ans;
int u[100005],v[100005],c[100005],col[100005];
int fa[100005];
struct node {int u,v,c,col;}edge[100005];
inline int read()
{int a=0,b=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch-'0');ch=getchar();}return a*b;
}
inline bool cmp(node a,node b){return a.c==b.c?a.colb.c;}
inline int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline bool kruskal(int x)
{int f1,f2,sum=0;for(rint i=1;i<=n;i++) fa[i]=i;for(rint i=1;i<=m;i++){edge[i].u=u[i];edge[i].v=v[i];edge[i].c=c[i];edge[i].col=col[i];if(!col[i]) edge[i].c+=x;}sort(edge+1,edge+m+1,cmp);for(rint i=1;i<=m;i++){f1=get(edge[i].u),f2=get(edge[i].v);if(f1!=f2){fa[f1]=f2;sum++;tot+=edge[i].c;if(!edge[i].col) cnt++;}if(sum==n-1)if(cnt>=need)return 1;else return 0;}
}
int main()
{n=read(),m=read(),need=read();for(rint i=1;i<=m;i++)u[i]=read()+1,v[i]=read()+1,c[i]=read(),col[i]=read();l=-101,r=101;while(l<r){tot=cnt=0;int mid=(l+r)>>1;if(kruskal(mid))l=mid+1,ans=tot-need*mid;else r=mid;}cout<endl;return 0;
}

View Code

T5太鼓达人：dfs欧拉回路

颓了题解，膜拜soul神佬。

一看题真的想不出来哪里和图论有关系……查了一下全说打表……

然后刷了一波学长题解，打了dfs过掉了。（我不是人我颓题解了……）

#include
#include
#include
#include
#include
#include
using namespace std;
int k,qyqyooo,ans[1<<13];
bool vis[(1<<13)+5];
inline bool dfs(int x,int len)
{if(vis[x])return 0;if(len==(1<return 1;ans[k+len-1]=x&1;int l=(x<<1),r=(x<<1)|1;vis[x]=1;if(dfs((x<<1)&qyqyooo,len+1)) return 1;if(dfs(((x<<1)|1)&qyqyooo,len+1)) return 1;vis[x]=0;return 0;
}
int main()
{scanf("%d",&k);qyqyooo=(1<1;dfs(0,1);printf("%d ",qyqyooo+1);for(int i=1;i<=qyqyooo+1;i++) printf("%d",ans[i]);return 0;
}

View Code

T6天天爱跑步：动态开点线段树+树上差分+LCA

写一个正经题解：

有两个式子，一个是si到LCA路径上满足wj的条件，另一个是在LCA到ti上的，这些大家感性理解一下就好。

这东西别的博客上都有，我就不放了（懒）我重点补大佬们的坑

首先为了求LCA做准备肯定要写一个dfs。不过我们还有别的用途，顺手求出dfs序。

目的是用一个区间来表示一个节点的子树方便后期统计。

然后对每一个点开一个线段树，线段树里面按照深度存的是当前节点所管辖的子树内的该深度的节点个数——的差分数组。（请理性的理解这句话三遍）

这很重要。

#include
#include
#include
#include
#include
#define rint register int
using namespace std;
struct node{int u,v,next;}edge[600005];
struct tree{int st,en,go;}lp[300005];
int n,tot_e,cnt,m,num,in_x,in_y,first[300005],deep[300005],ldfn[300005],rdfn[300005];
int lc[300005<<6],rc[300005<<6],w[300005],p[300005][22],ans[300005],root[300005<<6];
int qyqyooo[300005<<6],size[300005];
void add(int x,int y)
{tot_e++;edge[tot_e].u=x;edge[tot_e].v=y;edge[tot_e].next=first[x];first[x]=tot_e;
}
void dfs(int x)
{ldfn[x]=++num;size[x]=1;for(int i=first[x];i;i=edge[i].next){int v=edge[i].v;if(v==p[x][0])continue;p[v][0]=x;for(rint i=1;i<=20;++i)p[v][i]=p[p[v][i-1]][i-1];deep[v]=deep[x]+1;dfs(v);size[x]+=size[v];}rdfn[x]=num;
}/*
void get_fa()
{for(rint i=1;i<=n;i++) p[i][0]=fa[i];for(rint i=1;i<=20;i++)for(rint j=1;j<=n;j++)if(p[j][i-1]!=0)p[j][i]=p[p[j][i-1]][i-1];
}*/
int LCA(int x,int y)
{if(deep[x]<deep[y]) swap(x,y);int k=deep[x]-deep[y];for(rint i=20;i>=0;i--)if(k-(1<=0){k-=(1<<i);x=p[x][i];}if(x==y) return x;for(rint i=20;i>=0;i--)if(p[x][i]!=0&&p[x][i]!=p[y][i]){x=p[x][i];y=p[y][i];}return p[x][0];
}
void change(int x,int num,int le,int ri,int &now)
{if(x==0) return;if(now==0)now=++cnt;qyqyooo[now]+=num;if(le==ri) return;int mid=(le+ri)>>1;if(x<=mid)change(x,num,le,mid,lc[now]);else change(x,num,mid+1,ri,rc[now]);
}
int search(int lr,int rr,int le,int ri,int now)
{if(now==0) return 0;if(lr==le&&rr==ri) return qyqyooo[now];int mid=(le+ri)>>1;if(rr<=mid) return search(lr,rr,le,mid,lc[now]);if(lr>mid)return search(lr,rr,mid+1,ri,rc[now]);else return search(lr,mid,le,mid,lc[now])+search(mid+1,rr,mid+1,ri,rc[now]);
}int main()
{scanf("%d %d",&n,&m);for(rint i=1;i){scanf("%d %d",&in_x,&in_y);add(in_x,in_y);add(in_y,in_x);}for(rint i=1;i<=n;i++)scanf("%d",&w[i]);dfs(1);//get_fa();for(rint i=1;i<=m;i++){scanf("%d %d",&lp[i].st,&lp[i].en);lp[i].go=LCA(lp[i].st,lp[i].en);}for(rint i=1;i<=m;i++){change(ldfn[lp[i].st],1,1,n,root[deep[lp[i].st]]);change(ldfn[p[lp[i].go][0]],-1,1,n,root[deep[lp[i].st]]);}for(rint i=1;i<=n;i++)ans[i]+=search(ldfn[i],rdfn[i],1,n,root[deep[i]+w[i]]);for(rint i=1;i<=m;i++){change(ldfn[lp[i].en],1,1,n,root[deep[lp[i].st]-2*deep[lp[i].go]+2*n]);change(ldfn[lp[i].go],-1,1,n,root[deep[lp[i].st]-2*deep[lp[i].go]+2*n]);}for(rint i=1;i<=n;i++)ans[i]+=search(ldfn[i],rdfn[i],1,n,root[w[i]-deep[i]+2*n]);for(rint i=1;i<=n;i++)printf("%d ",ans[i]);return 0;
}

View Code

读者：欸怎么没了？

博主：溜——

T7软件安装：基环树：缩点+树型依赖背包dp

大体思路没什么大问题。

参数不要写错（不然w10），参数不要写错（不然w50），参数不要写错，(不然w70)，数组不要开小，（不然w80）

（我经历了啥）

#include
#include
#include
#include
#include
#include
#define rint register int
using namespace std;
int tot_e,cnt,n,m,w[202],v[202],d[202],dfn[202],low[202];
int tot_q,belong[202],qw[202],qv[202],first[202],deg[202];
int count[202],list[202],tpt=0,dp[202][505],first2[202],tot_e2;
bool instack[202];
struct node{int u,v,nxt;}edge[202],edge2[202];
struct data{int fa,lc,rc;}tree[202];
stack <int> s;
inline void add(int uu,int vv)
{++tot_e;edge[tot_e].u=uu;edge[tot_e].v=vv;edge[tot_e].nxt=first[uu];first[uu]=tot_e;
}
inline void add2(int uu,int vv)
{++tot_e2;edge2[tot_e2].u=uu;edge2[tot_e2].v=vv;edge2[tot_e2].nxt=first2[uu];first2[uu]=tot_e2;
}
inline void tarjan(int x)
{dfn[x]=low[x]=++cnt;s.push(x);instack[x]=true;for(rint i=first[x];i;i=edge[i].nxt){int y=edge[i].v;if(!dfn[y]){tarjan(y);low[x]=min(low[y],low[x]);}else if(instack[y])low[x]=min(dfn[y],low[x]);}if(dfn[x]==low[x]){++tot_q;while(1){int lin=s.top();s.pop();instack[lin]=false;belong[lin]=tot_q;qw[tot_q]+=w[lin];qv[tot_q]+=v[lin];if(lin==x) break;}}
}
inline void dfs(int x)
{for(rint i=first2[x];i;i=edge2[i].nxt){int to=edge2[i].v;dfs(to);for(rint j=m;j>=0;--j){for(rint p=0;p<=j;++p)dp[x][j]=max(dp[x][j],dp[to][p]+dp[x][j-p]);}}for(rint i=m;i>=0;--i){if(i>=qw[x]) dp[x][i]=dp[x][i-qw[x]]+qv[x];else dp[x][i]=0;}
}
int main()
{scanf("%d %d",&n,&m);for(rint i=1;i<=n;++i)scanf("%d",&w[i]);for(rint i=1;i<=n;++i)scanf("%d",&v[i]);for(rint i=1;i<=n;++i){scanf("%d",&d[i]);if(d[i]) add(d[i],i);}for(rint i=1;i<=n;++i)if(!dfn[i])tarjan(i);for(rint i=1;i<=n;++i){if(!d[i]) continue;if(belong[i]==belong[d[i]]) continue;add2(belong[d[i]],belong[i]);deg[belong[i]]++;}
/*for(rint x=1;x<=n;x++){if(!d[x])continue;for(rint i=first[x];i;i=edge[i].nxt){if(belong[x]==belong[edge[i].v])continue;add2(belong[x],belong[edge[i].v]);deg[belong[edge[i].v]]++;}}
*/for(rint i=1;i<=tot_q;i++)if(!deg[i])add2(tot_q+1,i);dfs(tot_q+1);cout<1][m]<<endl;return 0;
}

View Code