算法竞赛入门经典 写题笔记(第五章 图论算法与模型3)

算法竞赛入门经典 写题笔记(第五章 图论算法与模型3)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说算法竞赛入门经典 写题笔记(第五章 图论算法与模型3),希望能够帮助大家进步!!!

本节内容——

  • 生成树相关问题
  • 二分图最大匹配
  • 二分图最佳完美匹配
  • 稳定婚姻问题

知识点部分

例题20 秦始皇修路

秦朝有n(n<=1000)个城市,需要修建一些道路使得任意两个城市之间都可以联通。道士徐福生成他可以用法术修路,不花钱,也不用劳动力,但只能修一条路,因此需要慎重选择法术修建哪一条路。秦始皇不仅希望其他道路的总长度B尽量短(这样可以节省劳动力),还希望法术连接的两个城市的人口之和A尽量大,因此下令寻找一个A/B最大的方案。

我们可以先建立出最小生成树,然后枚举每条边(u,v),然后删除最小生成树上(u,v)之间的路径上的最大权\(maxcost[u][v]\)

现在的问题就是如何O(n)的求出来在最小生成树上到一个点的路径上的最大值。而这个也不难,一个dfs就完事了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 2010
using namespace std;
int n,m,t,T,cnt;
int head[MAXN],fa[MAXN];
double maxx[MAXN][MAXN];
struct Edge{int nxt,to;double dis;}edge[MAXN*MAXN];
struct Node{int x,y,w;}node[MAXN];
struct Line{int u,v;double dis;}line[MAXN*MAXN];
inline void add(int from,int to,double dis)
    {edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline bool cmp(Line x,Line y){return x.dis<y.dis;}
inline double dist(int a,int b)
    {return sqrt((node[a].x-node[b].x)*(node[a].x-node[b].x)+(node[a].y-node[b].y)*(node[a].y-node[b].y));}
inline void init(int now,int x,int pre,double cur_ans)
{
    maxx[now][x]=cur_ans;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        init(now,v,x,max(cur_ans,edge[i].dis));
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof(head));
        t=cnt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                line[++cnt]=(Line){i,j,dist(i,j)};
        sort(&line[1],&line[cnt+1],cmp);
        // for(int i=1;i<=cnt;i++) printf("dis[%d]=%.2lf\n",i,line[i].dis); 
        // cout<<endl;
        int sum=0;
        double all=0.0;
        for(int i=1;i<=cnt;i++)
        {
            int a=find(line[i].u),b=find(line[i].v);
            // printf("u=%d v=%d a=%d b=%d\n",line[i].u,line[i].v,a,b);
            if(a==b) continue;
            fa[a]=b;
            sum++;
            all+=line[i].dis;
            add(line[i].u,line[i].v,line[i].dis),add(line[i].v,line[i].u,line[i].dis);
            if(sum==n-1) break;
        }
        // printf("all=%.2lf\n",all);
        for(int i=1;i<=n;i++) init(i,i,-1,0);
        // for(int i=1;i<=n;i++)
        //     for(int j=i+1;j<=n;j++)
        //         printf("maxx[%d][%d]=%2.lf\n",i,j,maxx[i][j]);
        double ans=0.0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                ans=max(ans,1.0*(node[i].w+node[j].w)/(all-maxx[i][j]));
        printf("%.2lf\n",ans);
    }
    return 0;
}

例题21 邦德

有n座城市通过m条双向道路相连,每条道路都有一个危险系数。你的任务是回答若干个询问,每个询问包含一个起点s和一个终点t,要求找到一条从s到t的路,使得途径所有边的最大危险系数最小。

求最小瓶颈路。我们还可以按照上面那个题的思想,在dfs的时候更新到一个点的最值。
但是这样子是\(O(n^2)\)的。
看到数据范围想到\(log\)的时间复杂度——数据结构?好像不星啊。那就倍增吧......
挺好写的

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define MAXN 100010 using namespace std; int n,m,t,q,kase; int head[MAXN],fa[MAXN][20],maxx[MAXN][20],dep[MAXN],ff[MAXN]; struct Edge{int nxt,to,dis;}edge[MAXN<<1]; struct Line{int u,v,w;}line[MAXN<<1]; inline int find(int x){return x==ff[x]?x:ff[x]=find(ff[x]);} inline bool cmp(struct Line x,struct Line y){return x.w<y.w;} inline void add(int from,int to,int dis) { edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t; edge[++t].nxt=head[to],edge[t].to=from,edge[t].dis=dis,head[to]=t; } inline void dfs(int x,int pre) { dep[x]=dep[pre]+1; for(int i=head[x];i;i=edge[i].nxt) { int v=edge[i].to; if(v==pre) continue; maxx[v][0]=edge[i].dis; fa[v][0]=x; dfs(v,x); } } inline void init() { for(int j=1;j<=19;j++) { for(int i=1;i<=n;i++) { fa[i][j]=fa[fa[i][j-1]][j-1]; // printf("maxx[%d][%d]=max(%d %d)\n",i,j,maxx[i][j-1],maxx[fa[i][j-1]][j-1]); maxx[i][j]=max(maxx[i][j-1],maxx[fa[i][j-1]][j-1]); } } // for(int i=1;i<=n;i++) // for(int j=0;j<=2;j++) // printf("fa[%d][%d]=%d maxx[%d][%d]=%d\n",i,j,fa[i][j],i,j,maxx[i][j]); } inline int query(int x,int y) { // printf("x=%d y=%d\n",x,y); int cur_ans=0; if(dep[x]<dep[y]) swap(x,y); int cur=dep[x]-dep[y]; for(int i=19;i>=0;i--) if(cur&(1<<i)) { cur_ans=max(cur_ans,maxx[x][i]),x=fa[x][i]; // printf("cur_ans=%d x=%d\n",cur_ans,x); } if(x==y) return cur_ans; for(int i=19;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { cur_ans=max(cur_ans,maxx[x][i]); cur_ans=max(cur_ans,maxx[y][i]); x=fa[x][i],y=fa[y][i]; } } cur_ans=max(cur_ans,maxx[x][0]); cur_ans=max(cur_ans,maxx[y][0]); return cur_ans; } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif while(scanf("%d%d",&n,&m)==2) { if(kase==0) kase++; else puts(""); memset(head,0,sizeof(head)); memset(fa,0,sizeof(fa)); memset(maxx,0,sizeof(maxx)); memset(dep,0,sizeof(dep)); t=0; for(int i=1;i<=n;i++) ff[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&line[i].u,&line[i].v,&line[i].w); sort(&line[1],&line[m+1],cmp); int sum=0; for(int i=1;i<=m;i++) { int a=find(line[i].u),b=find(line[i].v); if(a!=b) { ff[a]=b; sum++; add(line[i].u,line[i].v,line[i].w); if(sum==n-1) break; } } // for(int i=1;i<=n;i++) // { // cout<<"i="<<i<<" "; // for(int j=head[i];j;j=edge[j].nxt) // cout<<edge[j].to<<" "; // cout<<endl; // } dfs(1,0); init(); scanf("%d",&q); while(q--) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",query(x,y)); } } return 0; }

例题22 比赛网络

你需要花费步超过cost元来搭建一个比赛网络。网络中有n台机器,编号为0~n-1,其中机器0为服务器,其他机器为客户机。一共有m条可以使用的网线,其中第i条网线的发送端是机器\(u_i\),接受端是机器\(v_i\)(数据只能从机器\(u_i\)单向传输到机器\(v_i\)),带宽为\(b_i Kbps\),费用为\(c_i\)元。每台客户机应当恰好从一台机器接受数据(即恰好有一条网线的接受端是该机器),而服务器不应从任何机器接受数据。你的任务是最大化网络中的最小带宽。

嘛.....就是二分带宽+最小有向生成树(最小树形图)判断.......
不会最小树形图的可以去我的学习笔记里面看OI树上问题 简单学习笔记QAQ

#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #define MAXN 100010 #define INF 0x3f3f3f3f using namespace std; int cost,T,ans; int top[MAXN],id[MAXN],minn[MAXN],fa[MAXN]; struct Edge{int u,v,dis,id,c;}edge[MAXN<<1],pre[MAXN<<1]; inline bool solve(int n,int m,int root) { ans=0; while(233) { int cnt=0; for(int i=1;i<=n;i++) id[i]=top[i]=fa[i]=0,minn[i]=INF; for(int i=1;i<=m;i++) { int u=edge[i].u,v=edge[i].v; if(u!=v&&edge[i].dis<minn[v]) fa[v]=u,minn[v]=edge[i].dis; } minn[root]=0; for(int i=1;i<=n;i++) { if(minn[i]==INF) return false; ans+=minn[i]; int u; for(u=i;u!=root&&top[u]!=i&&!id[u];u=fa[u]) top[u]=i; if(u!=root&&!id[u]) { id[u]=++cnt; for(int v=fa[u];v!=u;v=fa[v]) id[v]=cnt; } } if(!cnt) return true; for(int i=1;i<=n;i++) if(!id[i]) id[i]=++cnt; for(int i=1;i<=m;i++) { int u=edge[i].u,v=edge[i].v; int last=minn[v]; if((edge[i].u=id[u])!=(edge[i].v=id[v])) edge[i].dis-=last; } n=cnt,root=id[root]; } } inline bool check(int n,int m,int x) { int kkk=0; ans=0; for(int i=1;i<=m;i++) if(pre[i].c>=x) edge[++kkk]=pre[i]; // printf("x=%d\n",x); // for(int i=1;i<=kkk;i++) // printf("%d %d %d %d\n",edge[i].u,edge[i].v,edge[i].c,edge[i].dis); if(solve(n,kkk,1)==false) return false; // printf("ans=%d\n",ans); if(ans<=cost) return true; else return false; } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif scanf("%d",&T); int m,n; while(T--) { scanf("%d%d%d",&n,&m,&cost); // printf("n=%d m=%d cost=%d\n",n,m,cost); int l=INF,r=0,ansans=-1; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&pre[i].u,&pre[i].v,&pre[i].c,&pre[i].dis); // printf("%d d %d %d\n",pre[i].u,pre[i].v,pre[i].c,pre[i].dis); pre[i].u++,pre[i].v++; l=min(l,pre[i].c); r=max(r,pre[i].c); } // printf("l=%d r=%d\n",l,r); while(l<=r) { int mid=(l+r)>>1; if(check(n,m,mid)) ansans=mid,l=mid+1; else r=mid-1; } if(ansans==-1) printf("streaming not possible.\n"); else printf("%d kbps\n",ansans); } return 0; }

例题23 蚂蚁

给出n个白点和n个黑点的坐标,要求用n条不相交的线段把它们连接起来,其中每条线段恰好连接一个白点和一个黑点,每个点恰好连接到一条线段。
对于二维平面上的点,如果要用不相交的线连起来,最后线段总长度最小的方案(即二分图最佳完美匹配)就是解
题面pdf上的样例输出给错了。
我用的dinic跑的。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define MAXN 310 #define INF 1e9 #define S 0 #define T 2*n+1 using namespace std; int n,m,t=1,c; int head[MAXN],cur[MAXN],done[MAXN],pre_e[MAXN],pre_v[MAXN]; double f; double dis[MAXN]; struct Edge{int nxt,to,dis;double cost;}edge[MAXN*MAXN*2]; struct Node{int x,y;}node[MAXN]; inline double dist(int a,int b){ return sqrt(1.0*(node[a].x-node[b].x)*(node[a].x-node[b].x)+1.0*(node[a].y-node[b].y)*(node[a].y-node[b].y)); } inline void add(int from,int to,int dis,double cost) { edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,edge[t].cost=cost,head[from]=t; edge[++t].nxt=head[to],edge[t].to=from,edge[t].dis=0,edge[t].cost=-cost,head[to]=t; } inline bool spfa() { queue<int>q; for(int i=0;i<=T;i++) dis[i]=1e9; memset(done,0,sizeof(done)); q.push(S);dis[S]=0;done[S]=1; while(!q.empty()) { int u=q.front();q.pop();done[u]=0; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(edge[i].dis>0.0&&dis[u]+edge[i].cost<dis[v]) { dis[v]=dis[u]+edge[i].cost; pre_e[v]=i,pre_v[v]=u; if(!done[v]) q.push(v),done[v]=1; } } } if(dis[T]>=1e9) return false; int flow=0x3f3f3f3f; for(int i=T;i!=S;i=pre_v[i]) flow=min(flow,edge[pre_e[i]].dis); for(int i=T;i!=S;i=pre_v[i]) edge[pre_e[i]].dis-=flow,edge[pre_e[i]^1].dis+=flow; f+=flow; c+=flow*dis[T]; return true; } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif while(scanf("%d",&n)==1) { memset(head,0,sizeof(head)); t=1; for(int i=1;i<=n;i++) scanf("%d%d",&node[i].x,&node[i].y); for(int i=1;i<=n;i++) scanf("%d%d",&node[i+n].x,&node[i+n].y); for(int i=1;i<=n;i++) add(S,i,1,0);//printf("[%d %d] 1 0\n",S,i); for(int i=1;i<=n;i++) add(i+n,T,1,0);//printf("[%d %d] 1 0\n",i+n,T); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(i,j+n,1,dist(i,j+n));//printf("[%d %d] 1 %.2lf\n",i,j+n,dist(i,j+n)); while(spfa()); // printf("c=%d f=%.2lf\n",c,f); for(int i=1;i<=n;i++) { for(int j=head[i];j;j=edge[j].nxt) { if(edge[j].dis==0&&edge[j].to!=S) { printf("%d\n",edge[j].to-n); break; } } } } return 0; }

例题24 少林决胜

给定一个N*N的矩阵,每个格子里都有一个正整数\(w(i,j)\)。你的任务是给定每行确定一个整数\(row(i)\),每列也确定一个整数\(col(i)\),使得对于任意格子\((i,j)\)\(w(i,j)\le row(i)+col(j)\)。所有row(i)和col(i)之和应当尽量小。

“还记得KM算法里面的\(l(x)+l(y)>=w(x,y)\)吗?算法结束结束后,所有顶标和是最小的。”
......
于是跑一遍KM就行了QAQ

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define MAXN 510 #define INF 0x3f3f3f3f using namespace std; int n,kase,ans; int w[MAXN][MAXN],lx[MAXN],ly[MAXN],to[MAXN]; bool S[MAXN],T[MAXN]; inline int match(int x) { S[x]=true; for(int j=1;j<=n;j++) if(lx[x]+ly[j]==w[x][j]&&!T[j]) { T[j]=true; if(!to[j]||match(to[j])) { to[j]=x; return true; } } return false; } inline void update() { int d=INF; for(int i=1;i<=n;i++) if(S[i]) for(int j=1;j<=n;j++) if(!T[j]) d=min(d,lx[i]+ly[j]-w[i][j]); for(int i=1;i<=n;i++) { if(S[i]) lx[i]-=d; if(T[i]) ly[i]+=d; } } inline void KM() { for(int i=1;i<=n;i++) { lx[i]=ly[i]=to[i]=0; for(int j=1;j<=n;j++) lx[i]=max(lx[i],w[i][j]); } for(int i=1;i<=n;i++) { while(233) { for(int j=1;j<=n;j++) S[j]=T[j]=0; if(match(i)) break; else update(); } } } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif while(scanf("%d",&n)!=EOF) { ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&w[i][j]); KM(); for(int i=1;i<n;i++) printf("%d ",lx[i]),ans+=lx[i]; printf("%d\n",lx[n]),ans+=lx[n]; for(int i=1;i<n;i++) printf("%d ",ly[i]),ans+=ly[i]; printf("%d\n",ly[n]),ans+=ly[n]; printf("%d\n",ans); } return 0; }

例题25 固定分区内存管理

感觉和这个题差不多。
不过还要输出调度方案......具体请看代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #define MAXN 60 #define INF 0x3f3f3f3f using namespace std; int n,m,nm,kase; int start[MAXN],belong[MAXN]; int runtime[MAXN][MAXN],w[MAXN*10][MAXN*10]; int head[MAXN],siz[MAXN],s[MAXN],t[MAXN],number[MAXN]; int l[MAXN*10],lx[MAXN*10],ly[MAXN*10]; bool S[MAXN*10],T[MAXN*10]; vector<int>G[MAXN*10]; inline void add(int from,int to,int dis) { // printf("[%d %d] %d\n",from,to,dis); G[from].push_back(to); w[from][to]=dis; } inline bool match(int x) { S[x]=true; for(int i=0;i<G[x].size();i++) { int v=G[x][i]; if(lx[x]+ly[v]==w[x][v]&&!T[v]) { T[v]=true; if(!l[v]||match(l[v])) { l[v]=x; return true; } } } return false; } inline void update() { int d=INF; for(int i=1;i<=nm;i++) if(S[i]) for(int cur=0;cur<G[i].size();cur++) { int j=G[i][cur]; if(!T[j]) d=min(d,lx[i]+ly[j]-w[i][j]); } for(int i=1;i<=nm;i++) { if(S[i]) lx[i]-=d; if(T[i]) ly[i]+=d; } } inline void solve() { for(int i=1;i<=nm;i++) { lx[i]=ly[i]=l[i]=0; for(int j=1;j<=nm;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; } for(int i=1;i<=nm;i++) { while(233) { for(int j=1;j<=nm;j++) S[j]=T[j]=0; if(match(i)) break; else update(); } } } inline void print() { int all_time=0; for(int i=1;i<=m;i++) { vector<int>programs; for(int j=1;j<=n;j++) { int r=n*(i-1)+j; int cur=l[r]; if(cur>n) break; programs.push_back(cur); belong[cur]=i; all_time-=w[cur][r]; } reverse(programs.begin(),programs.end()); int cur_time=0; for(int j=0;j<programs.size();j++) { start[programs[j]]=cur_time; cur_time+=runtime[programs[j]][i]; } } printf("Case %d\n",++kase); printf("Average turnaround time = %.2lf\n",(double)all_time/n); for (int i=1;i<=n;i++) printf("Program %d runs in region %d from %d to %d\n",i,belong[i],start[i],start[i]+runtime[i][belong[i]]); printf("\n"); } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif while(scanf("%d%d",&m,&n)==2) { if(n==0&&m==0) break; nm=n*m; for(int i=1;i<=nm;i++) G[i].clear(); memset(w,0,sizeof(w)); for(int i=1;i<=m;i++) scanf("%d",&siz[i]); for(int i=1;i<=n;i++) { scanf("%d",&number[i]); for(int j=1;j<=number[i];j++) scanf("%d%d",&s[j],&t[j]); for(int j=1;j<=m;j++) { runtime[i][j]=-1; if(siz[j]<s[1]) continue; for(int k=1;k<=number[i];k++) { if(siz[j]<s[k+1]||k==number[i]) {runtime[i][j]=t[k];break;} } } } // for(int i=1;i<=n;i++) // for(int j=1;j<=m;j++) // printf("runtime[%d][%d]=%d\n",i,j,runtime[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(runtime[i][j]!=-1) for(int k=1;k<=n;k++) add(i,(j-1)*n+k,-runtime[i][j]*k); for(int i=n+1;i<=nm;i++) for(int j=1;j<=nm;j++) add(i,j,1); solve(); print(); } return 0; } 

例题26 女士的选择

稳定婚姻模板题

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1010
using namespace std;
int T,n,kase;
int to_girl[MAXN],to_boy[MAXN];
int a[MAXN][MAXN],order[MAXN][MAXN],nxt[MAXN];
queue<int>q;
inline void solve(int x,int y)
{
    int cur=to_boy[y];
    if(cur)
    {
        to_girl[cur]=0;
        q.push(cur);
    }
    to_girl[x]=y,to_boy[y]=x;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        while(!q.empty()) q.pop();
        memset(to_girl,0,sizeof(to_girl));
        memset(to_boy,0,sizeof(to_boy));
        if(!kase) kase++;
        else printf("\n");
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
            nxt[i]=1;
            q.push(i);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                int x;
                scanf("%d",&x);
                order[i][x]=j;
            }
        while(!q.empty())
        {
            int now=q.front();q.pop();
            int now_to=a[now][nxt[now]++];
            if(!to_boy[now_to]||order[now_to][now]<order[now_to][to_boy[now_to]]) 
                solve(now,now_to);
            else q.push(now);
        }
        for(int i=1;i<=n;i++) printf("%d\n",to_girl[i]);
    }
    return 0;
}

转载于:https://www.cnblogs.com/fengxunling/p/10851302.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29834

发表评论