【考试总结】99% 的中国人都不知道世上竟有这样的出题人，xzy 看了会沉默，boshi 看了会流泪——litble

于由litble发布

20171012 图论 test3

考试策略

看完题目，T1 和 T2 是做过的题，T4 有 60 分是最短路计数，但是好像改一改就可以过？T3 暂时没有思路。于是我就先快速打了 T1 和 T2，然后想出了 T4 的解法，写了 T4，再后来发现 T3 有 30 分是裸的最小生成树，再想了想写了个骗分一般的程序…… 结果 A 了？？（然而是因为数据水）

T1

期望得分：100 实际得分：100

题目描述：poj2186

题目分析：tarjan 缩点，然后如果入度为 0 的点只有一个，输出那个强连通分量的大小，否则输出 0.

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=10005,M=50005;
int n,m,tot,now,cn,top;
int h[N],to[M],ne[M],du[N],pos[N],low[N],dnf[N],ins[N],s[N],js[N];
void add(int x,int y){to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x){
    ++now;dnf[x]=low[x]=now;
    s[++top]=x,ins[x]=1;
    for(int i=h[x];i!=-1;i=ne[i])
        if(!dnf[to[i]])dfs(to[i]),low[x]=min(low[x],low[to[i]]);
        else if(ins[to[i]])low[x]=min(low[x],dnf[to[i]]);
    if(low[x]==dnf[x]){
        ++cn;int kl;
        do{
            kl=s[top],--top,pos[kl]=cn,ins[kl]=0,++js[cn];
        }while(kl!=x);
    }
}
int main()
{
    freopen("pop.in","r",stdin);
    freopen("pop.out","w",stdout);
    int i,x,y,bj=0,ans=0;
    n=read(),m=read();
    for(i=1;i<=n;++i)h[i]=-1;
    for(i=1;i<=m;++i)x=read(),y=read(),add(x,y);
    for(i=1;i<=n;++i)if(!dnf[i])dfs(i);
    for(x=1;x<=n;++x){
        if(du[pos[x]])continue;
        for(i=h[x];i!=-1;i=ne[i])
            if(pos[x]!=pos[to[i]]){du[pos[x]]=1;break;}
    }
    for(i=1;i<=cn;++i)
        if(!du[i]&&!bj)bj=1,ans=js[i];
        else if(!du[i]){ans=0;break;}
    printf("%d\n",ans);
    return 0;
}

T2

期望得分：100 实际得分：100

题目描述：HDU1598

题目分析：把边权从小到大排序，枚举边权最小的边，然后往后处理所有边。对于每一条边，将此边相连的两个点加入同一个并查集，当 s 和 t 属于同一个并查集

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=205,M=1005;
int n,m,q;
struct node{int x,y,w;}e[M];
int f[N];
bool cmp(node a,node b){return a.w<b.w;}
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    int i,j,s,t,ans,r1,r2;
    while(~scanf("%d%d",&n,&m)){
        for(i=1;i<=m;++i)e[i].x=read(),e[i].y=read(),e[i].w=read();
        sort(e+1,e+1+m,cmp);q=read();
        while(q--){
            s=read(),t=read(),ans=1e9;
            for(i=1;i<=m;++i){
                for(j=1;j<=n;++j)f[j]=j;
                for(j=i;j<=m;++j){
                    r1=find(e[j].x),r2=find(e[j].y);
                    if(r1!=r2){
                        f[r1]=r2;
                        if(find(s)==find(t)){
                        if(ans>e[j].w-e[i].w)ans=e[j].w-e[i].w;
                        break;}
                    }
                }
            }
            if(ans<1e9)printf("%d\n",ans);
            else puts("-1");
        }
    }
    return 0;
}

T3

期望得分：30 实际得分：100（然而是因为数据水）

题目描述：poj1639

题目分析：

我…… 我不会度限制生成树…… 我…… 我在最小生成树的时候判断如果和公园相连的边已经选了 k 条，就不选和公园相连的边了…… 我…… 我 A 了这题……

好吧，说一说正解。

应该看得出题目是一个 Park 度数小于等于 k 的最小生成树吧？

首先，我们去掉所有与 Park 相连的边，假设图被分成了 m 块，那么就弄 m 个最小生成树出来。再选 m 条最小的边让 m 块与 Park 相连，这个时候我们得到了 Park 的最小度生成树。

然后我们添加新的与 Park 相连的边。每次 dfs 一遍生成树，记录 Park 到每一个点的路径上的最长的那一条（当然不能是与 Park 相连的某一条），然后就可以算出添加一条新的与 Park 相连的边可以使当前答案减小的最大值，去掉该去的边，加上该加的边，重复此过程，直到与 Park 相连的边为 k 条或是不能使得答案减小为止。

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<map>
using namespace std;
int n,m,lim,ans,nowk;
map<string,int>name;
struct node{int x,y,w;}e[405];
int l[25][25],f[25],g[25][25],a[25],pre[25];
bool cmp(node a,node b){return a.w<b.w;}
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);return f[x];
}
void work1(){
    int i,r1,r2;
    sort(e+1,e+1+m,cmp);
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        if(e[i].x==1||e[i].y==1)continue;
        r1=find(e[i].x),r2=find(e[i].y);
        if(r1!=r2){
            f[r1]=r2,ans+=e[i].w;
            g[e[i].x][e[i].y]=g[e[i].y][e[i].x]=1;
        }
    }
}
int dp[25],u[25],v[25];
void dfs(int x,int las){
    for(int i=1;i<=n;++i){
        if(i==las)continue;
        if(!g[x][i])continue;
        if(dp[i]!=-1){
            if(dp[x]==-1||dp[x]<l[x][i])
                dp[i]=l[x][i],u[i]=x,v[i]=i;
            else dp[i]=dp[x],u[i]=u[x],v[i]=v[x];
        }
        dfs(i,x);
    }
}
void work2(){
    int i,r1,j,mx,bj;
    for(i=1;i<=n;++i)a[i]=1e8;
    for(i=1;i<=n;++i){
        if(l[1][i]==-1)continue;
        r1=find(i);if(a[r1]>l[1][i])a[r1]=l[1][i],pre[r1]=i;
    }
    for(i=1;i<=n;++i)if(pre[i]){
        g[1][pre[i]]=g[pre[i]][1]=1;
        ans+=l[1][pre[i]],++nowk;
    }
    for(i=nowk+1;i<=lim;++i){
        for(j=1;j<=n;++j){
            if(g[1][j])dp[j]=-1;
            else dp[j]=0;
        }
        dfs(1,0),mx=0;
        for(j=1;j<=n;++j){
            if(l[1][j]==-1||g[1][j])continue;
            if(l[1][j]-dp[j]<mx)mx=l[1][j]-dp[j],bj=j;
        }
        if(mx>=0)break;ans+=mx;
        g[u[bj]][v[bj]]=g[v[bj]][u[bj]]=0;
        g[1][bj]=g[bj][1]=1;
    }
}
int main(){
    freopen("park.in","r",stdin);
    freopen("park.out","w",stdout);
    int i;string s1,s2;
    memset(l,-1,sizeof(l));
    scanf("%d",&m);name["Park"]=1;n=1;
    for(i=1;i<=m;++i){
        cin>>s1>>s2>>e[i].w;
        if(!name[s1])name[s1]=++n;
        if(!name[s2])name[s2]=++n;
        e[i].x=name[s1],e[i].y=name[s2];
        l[e[i].x][e[i].y]=l[e[i].y][e[i].x]=e[i].w;
    }
    scanf("%d",&lim);work1();work2();
    printf("Total miles driven: %d",ans);
    return 0;
}

T4

期望得分：100 实际得分：100

题目描述：poj3463

题目分析-方法 1：

首先在反向图上从 t 开始跑一遍 spfa，得到每一个点到终点的最短路。然后记忆化搜索，f[x] 表示从 x 到 t 的最短路数量，g[x] 表示从 x 到 t 的比最短路长 1 的路的数量，状态转移看代码吧。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=1005,M=10005;
int tot,n,m,t1,s,t,T;
int h[N],ne[M],to[M],w[M],h1[N],ne1[M],to1[M],w1[M];
int dis[N],inq[N],vis[N];
long long f[N],g[N];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void add1(int x,int y,int z)
{to1[++t1]=y,ne1[t1]=h1[x],h1[x]=t1,w1[t1]=z;}
void spfa(){
    queue<int>q;int i,x;
    for(i=1;i<=n;++i)dis[i]=1e8,inq[i]=0;
    dis[t]=0,q.push(t);
    while(!q.empty()){
        x=q.front(),q.pop(),inq[x]=0;
        for(i=h1[x];i!=-1;i=ne1[i])
            if(dis[x]+w1[i]<dis[to1[i]]){
            dis[to1[i]]=dis[x]+w1[i];
            if(!inq[to1[i]])inq[to1[i]]=1,q.push(to1[i]);
        }
    }
}
void dfs(int x){
    if(vis[x])return;
    vis[x]=1;if(x==t)return;
    for(int i=h[x];i!=-1;i=ne[i]){
        if(w[i]+dis[to[i]]==dis[x])
            dfs(to[i]),g[x]+=g[to[i]],f[x]+=f[to[i]];
        else if(w[i]+dis[to[i]]==dis[x]+1)
            dfs(to[i]),g[x]+=f[to[i]];
    }
}
int main()
{
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    int i,x,y,z;
    T=read();
    while(T--){
        n=read(),m=read();tot=t1=0;
        for(i=1;i<=n;++i)h[i]=h1[i]=-1,f[i]=g[i]=vis[i]=0;
        for(i=1;i<=m;++i){
            x=read(),y=read(),z=read();
            add(x,y,z),add1(y,x,z);
        }
        s=read(),t=read();spfa();
        if(dis[s]>=1e8){puts("0");return 0;}
        f[t]=1;dfs(s);
        printf("%lld\n",f[s]+g[s]);
    }
    return 0;
}

题目分析-方法 2**：

呃，所以为什么其他人都是在 dijkstra 的时候顺便求次短路和计数呐？

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1005,M=10005;
int T,tot,n,m,s,t;
int h[N],ne[M],to[M],w[M];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int dis[N][2],c[N][2],vis[N][2];
void work(){
    int i,j,flag,k,mx,l,v;
    for(i=1;i<=n;++i){
        dis[i][0]=dis[i][1]=1e8;
        c[i][0]=c[i][1]=vis[i][0]=vis[i][1]=0;
    }
    dis[s][0]=0,c[s][0]=1;
    for(i=1;i<=2*n-1;++i){
        k=-1,mx=1e8;
        for(j=1;j<=n;++j)
            if(!vis[j][0]&&dis[j][0]<mx)
                mx=dis[j][0],k=j,flag=0;
            else if(!vis[j][1]&&dis[j][1]<mx)
                mx=dis[j][1],k=j,flag=1;
        if(k==-1)break;
        vis[k][flag]=1;
        for(j=h[k];j!=-1;j=ne[j]){
            l=dis[k][flag]+w[j],v=to[j];
            if(l<dis[v][0]){
                dis[v][1]=dis[v][0],c[v][1]=c[v][0];
                dis[v][0]=l,c[v][0]=c[k][flag];
            }
            else if(l==dis[v][0])c[v][0]+=c[k][flag];
            else if(l<dis[v][1])dis[v][1]=l,c[v][1]=c[k][flag];
            else if(l==dis[v][1])c[v][1]+=c[k][flag];
        }
    }
}
int main(){
    int i,x,y,z;
    scanf("%d",&T);
    while(T--){
        memset(h,-1,sizeof(h));tot=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
        scanf("%d%d",&s,&t);work();
        if(dis[t][1]==dis[t][0]+1)c[t][0]+=c[t][1];
        printf("%d\n",c[t][0]);
    }
    return 0;
}
分类： 文章

litble

苟...苟活者在淡红的血色中，会依稀看见微茫的希望

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注