【考试总结】图论 Test3(20171002) 解题报告——蒟蒻 XZY

于由XZYQvQ发布

图论 Test3(20171002) 解题报告——蒟蒻 XZY

蒟蒻：警察叔叔！就是那个出题人！听了我的算法就改数据来卡我！

警察：我从未见过有如此厚颜无耻之出题人！

T1

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

题目来源：POJ – 2186

题解：kosaraju强联通分量缩点后，设出度为0的点个数为cnt。如果cnt>1 则直接输出 0（因为任意两个出度为 0 的点互相不能到达，即不可能有点可以满足所有点都能到达它）。如果 cnt=1，很显然，就是出度为 0 的那个强联通分量内的所有点。

代码：

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define NS (10005)
#define MS (50005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
    int head[NS],nxt[MS],to[MS],cnt;
    void init(){memset(head,-1,sizeof(head)),cnt=0;}
    void push(int a,int b)
    {
        nxt[cnt]=head[a],to[cnt]=b,head[a]=cnt++;
    }
}g1,g2;
int n,m,cnt,scc[NS],tot,ans;
bool book[NS];
stack<int> st;
void initdfs(int a)
{
    book[a]=1;
    for(int i=g1.head[a];i!=-1;i=g1.nxt[i])
        if(!book[g1.to[i]])initdfs(g1.to[i]);
    st.push(a);
}
void dfs(int a)
{
    book[a]=1,scc[a]=cnt;
    for(int i=g2.head[a];i!=-1;i=g2.nxt[i])
        if(!book[g2.to[i]])dfs(g2.to[i]);
}
int main()
{
    freopen("pop.in","r",stdin),freopen("pop.out","w",stdout);
    g1.init(),g2.init(),IN(n),IN(m);
    for(int i=1,a,b;i<=m;i++)IN(a),IN(b),g1.push(a,b),g2.push(b,a);
    for(int i=1;i<=n;i++)if(!book[i])initdfs(i);
    memset(book,0,sizeof(book));
    while(!st.empty())
    {
        int t=st.top();st.pop();
        if(!book[t])cnt++,dfs(t);
    }
    tot=cnt;
    for(int i=1;i<=n;i++)
        for(int j=g1.head[i];j!=-1;j=g1.nxt[j])
            if(scc[i]!=scc[g1.to[j]])
                tot-=book[scc[i]],book[scc[i]]=0;
    if(tot>1)printf("0\n"),exit(0);
    for(int i=1;i<=cnt;i++)
        if(book[i])
            for(int j=1;j<=n;j++)if(scc[j]==i)ans++;
    printf("%d\n",ans);
    return 0;
}

T2

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

题目来源：HDU – 1598

题解：枚举最小生成树中最小边是哪条，然后生成最小生成树，输出所有最小生成树的最长边与最短边的差值中最小值

代码：

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct edge
{
    int u,v,l;
    bool operator < (const edge another)const
    {
        return l<another.l;
    }
}e[1005];
int n,m,q,f[205],s,t;
int findf(int a){return f[a]==a?a:f[a]=findf(f[a]);}
int main()
{
    freopen("road.in","r",stdin),freopen("road.out","w",stdout);
    IN(n),IN(m);
    for(int i=1;i<=m;i++)IN(e[i].u),IN(e[i].v),IN(e[i].l);
    sort(e+1,e+1+m),IN(q);
    while(q--)
    {
        IN(s),IN(t);
        int ans=INT_MAX;
        for(int k=1,lst;k<=m;k++)
        {
            for(int i=1;i<=n;i++)f[i]=i;
            for(int i=k,fa[2];i<=m;i++)
            {
                fa[0]=findf(e[i].u),fa[1]=findf(e[i].v);
                if(fa[0]==fa[1])continue;
                lst=i,f[fa[0]]=fa[1];
                if(findf(s)==findf(t))break;
            }
            if(findf(s)!=findf(t))break;
            ans=min(ans,e[lst].l-e[k].l);
        }
        if(ans==INT_MAX)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

T3

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

题目来源：POJ – 1639

题解：显然我和 kb 是一模一样的错误解法。只是数据太水 A 了。错解就不说了。

正解是 “最小 度限制 生成树”（注意断句）

具体算法思路是先把 park 删除，然后跑最小生成树。这时候图不一定联通了。我们设有 M 个联通块，那我们就让这 M 个联通块每个都连一条边到 park 使得图联通。对于每个联通块可能有多个边通向 park，我们选择长度最小的那条。这时候我们得到了最小 M 度生成树。然后我们枚举所有链接 park 却没有用上的边，尝试联通它。因为联通它之后会导致生成树变成图（即多了 1 条边），我们就去枚举删除哪条边。因为我们要让总权值最小，所以我们要让删掉的边权值最大。寻找最大边可以用动态规划（dfs）解决。我们选择一条链接 park 却没有用上的边，使得这条边的权值减去删掉的边的权值最小，这样可以让答案变小得更多。至于删除的边，必须是删除后可以使得整个图具有树的性质的。假设我们链接了一条从 park 到 i 的边，那么我们删除的边显然在 park 到 i 的路径上。这里用很简单的动归解决。

重复这个过程，直到 park 出度为 k 或者答案已经不能更小为止。

代码：

#include <iostream>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
using namespace std;
struct query{string s1,s2;int l;}Q[1000];
struct edge
{
    int u,v,l;
    bool operator < (const edge another)const
    {
        return l<another.l;
    }
}e[1005];
int m,n,k,park,dis[25][25],tmp[25],x[25],y[25],dt,ans,f[25];
set<string> h;
map<string,int> h2;
bool book[25][25];
int cindf(int a){return f[a]==a?a:f[a]=cindf(f[a]);}
void dfs(int a,int fa)
{
    for(int i=1;i<=n;i++)
        if(book[a][i]&&i!=fa)
        {
            if(tmp[i]!=-1)
            {
                if(tmp[a]>dis[a][i])
                    tmp[i]=tmp[a],x[i]=x[a],y[i]=y[a];
                else tmp[i]=dis[a][i],x[i]=a,y[i]=i;
            }
            dfs(i,a);
        }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>Q[i].s1>>Q[i].s2>>Q[i].l,h.insert(Q[i].s1),h.insert(Q[i].s2);
    for(set<string>::iterator i=h.begin();i!=h.end();i++)h2[*i]=++n;
    park=h2["Park"];
    for(int i=1;i<=m;i++)
    {
        e[i].u=h2[Q[i].s1],e[i].v=h2[Q[i].s2],e[i].l=Q[i].l;
        dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].l;
    }
    sort(e+1,e+1+m),cin>>k;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(e[i].u==park||e[i].v==park)continue;
        int fa[2]={cindf(e[i].u),cindf(e[i].v)};
        if(fa[0]==fa[1])continue;
        ans+=e[i].l,f[fa[0]]=fa[1];
        book[e[i].u][e[i].v]=book[e[i].v][e[i].u]=1;
    }
    dis[0][park]=dis[park][0]=INT_MAX;
    for(int i=1;i<=n;i++)
        if(dis[i][park]&&dis[i][park]<dis[tmp[cindf(i)]][park])
            tmp[cindf(i)]=i;
    for(int i=1;i<=n;i++)
        if(i!=park&&cindf(i)==i)
            book[tmp[i]][park]=book[park][tmp[i]]=1,ans+=dis[tmp[i]][park],dt++;
    for(int i=dt+1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)if(book[park][j])tmp[j]=-1;else tmp[j]=0;
        dfs(park,0);
        int mxi,mxn=0;
        for(int j=1;j<=n;j++)
            if(dis[j][park]&&!book[j][park])
                if(dis[j][park]-tmp[j]<mxn)mxn=dis[j][park]-tmp[j],mxi=j;
        if(mxn==0)break;
        ans+=mxn;
        book[x[mxi]][y[mxi]]=book[y[mxi]][x[mxi]]=0;
        book[park][mxi]=book[mxi][park]=1;
    }
    cout<<"Total miles driven: "<<ans<<endl;
    return 0;
}

T4

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

题目来源：POJ – 3463

题解：一开始想着写记忆化搜索，却想不出（我太弱了）。突然发现比最短路长 1 其实就是次短路，因此。。。我们可以用上 A*算法（这个在我出的图论测试 1 中出现过）。

我们弄个优先队列，每次取出（“起点到这个点的路径长度”+“这个点到终点的最短路长度”）最小的点进行扩展。第一次扩展到终点就是最短路。第二次扩展到终点的时候可能是最短路（可能最短路不止 1 条），也可能是次短路。然后我们就这样一条一条路径数。因为这样子第 i 次扩展到终点时路径长度一定是排名第 i 的（长度相同的谁拍前面随便）。

然而。。。abs 考场把这个做法报出来了！当着制杖出题人的面！

然后出题人就开始卡这种做法——因为这种做法当答案较大时就 gg 了。

然而道高一尺，魔高一丈，我猜测——zz 出题人必然会搞很多重边，导致答案陡然增加！于是我加了一个优化：记录每条边重复的次数，也就是把所有的重边合并到一起，然后路径条数统计时就不一条一条数，而是将重边数乘起来。比如从 1 到 2 有两条重边，2 到 3 有 3 条重边，那么 1 到 3 就有 2×3=6 种走法！

显然，zz 出题人无法卡掉我了。

然而，处于好心，我把我的优化告诉了出题人！

于是他又临时决定卡我的优化！

但是由于时间问题与舆论压力，所以他就没有卡我了。

我就 AC 了。

代码：

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define NS (1005)
#define MS (10005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
    int head[NS],nxt[MS],to[MS],d[MS],tot[MS],cnt;
    void init(){memset(head,-1,sizeof(head)),cnt=0;}
    void push(int a,int b,int c,int T)
    {
        nxt[cnt]=head[a],to[cnt]=b,d[cnt]=c,tot[cnt]=T,head[a]=cnt++;
    }
}g1,g2;
struct st
{
    int u,l,tot;
    bool operator < (const st another)const
    {
        return l>another.l;
    };
};
int n,m,s,t,dis[NS],ans,minl=2e6+5;
bool book[NS];
queue<int> que;
priority_queue<st> pq;
map<int,int> MP[1005][1005];
int main()
{
    freopen("travel.in","r",stdin),freopen("travel.out","w",stdout);
    g1.init(),g2.init(),IN(n),IN(m);
    for(int i=1,a,b,c;i<=m;i++)
        IN(a),IN(b),IN(c),MP[a][b][c]++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(MP[i][j].size())
                for(map<int,int>::iterator it=MP[i][j].begin();it!=MP[i][j].end();it++)
                    g1.push(i,j,it->first,it->second),g2.push(j,i,it->first,it->second);
    for(int i=1;i<=n;i++)dis[i]=3e6;
    IN(s),IN(t),dis[t]=0,que.push(t),book[t]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop(),book[F]=0;
        for(int i=g2.head[F];i!=-1;i=g2.nxt[i])
            if(dis[g2.to[i]]>dis[F]+g2.d[i])
            {
                dis[g2.to[i]]=dis[F]+g2.d[i];
                if(!book[g2.to[i]])que.push(g2.to[i]),book[g2.to[i]]=1;
            }
    }
    pq.push((st){s,dis[s],1});
    while(!pq.empty())
    {
        st F=pq.top();pq.pop();
        int u=F.u,l=F.l,tot=F.tot;
        if(l-minl>1)break;
        if(u==t)ans+=tot,minl=min(minl,l);
        int p=l-dis[u];
        for(int i=g1.head[u];i!=-1;i=g1.nxt[i])
            pq.push((st){g1.to[i],p+g1.d[i]+dis[g1.to[i]],tot*g1.tot[i]});
    }
    printf("%d\n",ans);
    return 0;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

piano · 2017年10月14日 8:51 下午

~xzy 太厉害啦，ak 啦~

回复

    konnyakuxzy · 2017年10月16日 7:49 下午

    您没发现这题比较水吗？
    而且只能怪出题人啊。。。数据太水了，T3 最小生成树都过了。。。而且 T3 我一开始少输出了个空格暴零了。。。后来好 (ji) 心 (xing) 的出题人帮我复制了一下代码搞了个副本才过的。。。
    我还是太弱了，还是您强%%%%%%

    回复

发表回复

Avatar placeholder

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