您的位置: 首页 > IT文章 > 「题解」：图论专题总结

「题解」：图论专题总结

分类: IT文章 • 2023-11-25 09:31:01

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

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

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

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

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

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#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!"<<endl;continue;}
        while(!q.empty())
        {
            int xx=q.top();s.push(xx);q.pop();
//            cout<<xx<<endl;
            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"<<yy<<endl;
                    vis[yy]=1;
                }
            }
//            if(pan==0&&q.empty()){cout<<"Impossible!"<<endl;break;}
        }
//        if(pan==0)continue;
        if(s.size()!=n){cout<<"Impossible!"<<endl;continue;}
        while(!s.empty())
        {
            cout<<s.top()<<' ';
            s.pop();
        }
        cout<<endl;
    }
}

View Code

T2矩阵游戏：二分图

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

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

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

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

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

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
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<<ans<<endl;
        if(ans!=n){
            printf("No
");
        }
        else puts("Yes
");
    }
}

View Code

T3约会 Rendezvous：基环树

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

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#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<dell[i].size();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<dell[i].size();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
");
        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
",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]]<l_a[bl[y]]) ans1=edge+ll,ans2=r,ans3=edge,ans4=r+rr;
            else ans1=edge+rr,ans2=r,ans3=edge,ans4=r+ll;
            if(max(ans1,ans2)<max(ans3,ans4)) printf("%d %d
",ans1,ans2);
            else if(max(ans1,ans2)>max(ans3,ans4)) printf("%d %d
",ans3,ans4);
            else
            {
                if(min(ans1,ans2)<min(ans3,ans4)) printf("%d %d
",ans1,ans2);
                else if(min(ans1,ans2)>min(ans3,ans4)) printf("%d %d
",ans3,ans4);
                else printf("%d %d
",max(ans1,ans2),min(ans1,ans2));
            }
        }
    }
    return 0;
}

View Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<algorithm> #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.col<b.col:a.c<b.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<<ans<<endl; return 0; }

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> 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<<k))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<<k)-1; dfs(0,1); printf("%d ",qyqyooo+1); for(int i=1;i<=qyqyooo+1;i++) printf("%d",ans[i]); return 0; }

#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cmath> #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<<i)>=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<n;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; }

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #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<<dp[tot_q+1][m]<<endl; return 0; }

「题解」：图论专题总结

相关推荐