51nod图论题解（4级，5级算法题）

2022-11-13 16:47:04

51nod图论题解（4级，5级算法题）

1805 小树

基准时间限制：1.5 秒空间限制：131072 KB 分值: 80 难度：5级算法题

她发现她的树的点上都有一个标号（从1到n），这些树都在空中飘浮不在土地上生根，然而每天她的这些树会变化一个形态，这使得她很恼火，她想弄清楚到底有多少种形态。

特殊的是这些树的叶子（度数为1）数目是不变的。

由于数目可能很大，她只要它模（1,000,000,007）就可以了。

n=3,m=2时有3种方案：1-2-3, 2-3-1,3-1-2. 3-1-2和2-1-3属于同一种。

Input

一共一行，第一行包含两个数n,m分别表示点的总个数和叶子数。

2<=n,m<=1,000,000。

数据保证树一定存在。

Output

一共一行，输出方案数。

Input示例

5 3

Output示例

60

题目解析

首先介绍一下Cayley公式，即是一个无根树有n^（n-2）种同构，这是根据Prüfer编码获得的结论，具体证明请看这里，给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。所以我们可以看出来，出现在Cayley公式中的编号初始一定不是叶子节点。那么我们只需要通过容斥定理来计算一下有n-m个非叶子节点构成的序列种数就行了。

公式

ans = C(0,n-m)(n-m)^(n-2) - C(1,n-m)(n-m-1)^(n-2) + C(2,n-m)(n-m-2)^(n-2) - C(3,n-m)(n-m-3)^(n-2).....

代码

#include<bits\stdc++.h>

using namespace std;

#define LL long long

const int maxn = 1000100;

const LL Mod = 1e9 + 7;

LL jc[maxn];

LL ny[maxn];

LL ksm(LL x,LL y)

{

    LL ans = 1;

    while(y){

        if(y&1){

            ans = ans*x%Mod;

        }

        y >>= 1;

        x = x*x%Mod;

    }

    return ans;

}

LL getc(LL n,LL m)

{

    if( m == 0 || n == m)

        return 1;

    return (jc[n]*ny[m]%Mod)*ny[n-m]%Mod;

}

void pre(int n)

{

    jc[1] = ny[1] = 1;

    for(int i = 2; i <= n; i++){

        jc[i] = i * jc[i-1] % Mod;

        ny[i] = (Mod - Mod/i) * ny[Mod%i] % Mod;

    }

    for(int i = 2; i <= n; i++){

        ny[i] = ny[i] * ny[i-1] % Mod;

    }

}

int main()

{

    LL ans = 0;

    LL n,m;

    cin>>n>>m;

    pre(n);

    LL c = getc(n,m);

    LL k = n - m;

    while(k){

        if((k&1) == ((n-m)&1))

            ans = (ans+ getc(n-m,k) * ksm(k,n-2) % Mod )% Mod;

        else

            ans = (Mod + ans - getc(n-m,k) * ksm(k,n-2) % Mod)% Mod;

        k--;

    }

    if(n == 2 && m == 2)

        cout<<1<<endl;

    else

        cout<<c*ans%Mod<<endl;

    return 0;

}

1835 完全图

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

初始有n个点，任意两个点之间有一条无向边，现在要移除一些无向边（至少一条），问移除后有恰好m个连通块的方案数是多少。

两个方案不同当且仅当存在至少一条无向边在某个方案中被移除，但是在另一个方案中没被移除。

答案可能很大请模一个998,244,353。

Input

第一行读入n,m。

1<=m<=n<=500

Output

第一行输出方案数。

Input示例

3 2

Output示例

3

题目解析

一道DP加容斥的题目，DP[i][j]表示i个点构成j个联通块的方案数

然后我们可以将i个点构成j个联通块分解为i-k个点构成j-1个联通块 与 含有第一个点的k个点构成1个联通块 (枚举点1所在的联通块的大小，直接枚举C(k,i)会有重复)。所以我们得到如下dp方程

DP[i][j] = ∑(1<=k<=i-j+1)(C(k-1,i-1) * DP[k][1] * DP[i-k][j-1])###

值得注意的是DP[n][1] 不能通过这个公式获得，但是很明显

DP[n][1] = 2^(n*(n+1)/2) - ∑(2<=i<=n)DP[n][i]

另外一点就是m = 1时，DP[n][1] 包括了一种情况，一条边都不删，我们需要特判删除这一种情况

代码

#include<bits\stdc++.h>

using namespace std;

#define CLR(a,b) memset(a,b,sizeof(a)

#define LL long long

const LL Mod = 998244353;

LL jc[510];

LL ny[510];

LL ksm(LL x,LL y)

{

    LL ans = 1;

    while(y){

        if(y&1){

            ans = ans * x % Mod;

        }

        y >>= 1;

        x = x * x % Mod;

    }

    return ans;

}

LL getc(LL n,LL m)

{

    if(m == 0 || m == n)

        return 1;

    else

        return ( jc[n] * ny[m] % Mod ) * ny[n-m] % Mod;

}

LL pre(int n)

{

    jc[1] = ny[1] = 1;

    jc[0] = ny[0] = 1;

    for(int i = 2; i <= n; i++){

        jc[i] = jc[i-1] * i % Mod;

        ny[i] = (Mod - Mod/i) * ny[Mod%i] % Mod;

    }

    for(int i = 2; i <= n; i++){

        ny[i] = ny[i] * ny[i-1] % Mod;

    }

}

LL dp[510][510];

int main()

{

    int n,m;

    cin>>n>>m;

    pre(n);

    dp[1][1] = 1;

    for(int i = 2; i <= n; i++){

        for(int j = i; j >= 2; j--){

            for(int k = 1; k <= i - j + 1; k++){

                dp[i][j] = ( dp[i][j] + ( getc(i-1,k-1) * dp[k][1] % Mod ) * dp[i-k][j-1] % Mod ) % Mod;

            }

        }

        dp[i][1] = ksm(2,(i*(i-1))/2);

        for(int k = 2; k <= i; k++){

            dp[i][1] = ( dp[i][1] - dp[i][k] + Mod ) % Mod;

        }

    }

    if( m != 1)

        cout<<dp[n][m]<<endl;

    else

        cout<<dp[n][m]-1<<endl;

    return 0;

}

1967 路径定向

基准时间限制：1.2 秒空间限制：262144 KB 分值: 80 难度：5级算法题

给出一个有向图，要求给每条边重定向，使得定向后出度等于入度的点最多，输出答案和任意一种方案

Input

第一行两个正整数N，M，表示1-N号点与M条边

接下来M行，每行两个正整数Xi，Yi，表示存在一条有向边从Xi指向Yi

N≤10^5, M≤3*10^5, Xi,Yi≤N

Output

第一行一个整数Ans，表示定向后出度等于入度的最大点数

第二行一个长度为M的01字符串，第i位为0表示第i条边不改向，第i位为1表示第i条边改变方向

Input示例

7 7

1 2

2 3

2 3

4 5

1 5

6 7

6 7

Output示例

5

0010110

题目解析

既然我们可以改变边的方向，那么我们可以把这个图视为无向图，我们把所有度数为奇数的点之间每两点连一条线，然后！！！！无向图，所有点都是偶点，没错是你，欧拉回路，直接跑dfs遍历，欧拉回路的每个点的入度都等于出度，也就是说原图的偶点都满足条件，最多。至于奇点，永远不可能入度等于出度。记录一下边的方向输出就行了。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

struct Edge

{

    int v;

    int num;

    int dir;

    Edge(int v,int num,int dir)

    {

        this->v = v;

        this->num = num;

        this->dir =dir;

    }

};

vector<Edge> edge[maxn];

int deg[maxn];

int c[maxn];

int vis[maxn];

int cnt = 0;

void dfs(int st)

{

    vis[st] = 1;

    for(int i = 0; i < edge[st].size(); i++){

        Edge now = edge[st][i];

        if(c[now.num] == -1 ){

            cnt++;

            if(now.dir == 1)

                c[now.num] = 1;

            else

                c[now.num] = 0;

            dfs(now.v);

        }

    }

}

int main()

{

//    freopen("in.txt","r",stdin);

    ios::sync_with_stdio(false);

    int n,m;

    cin>>n>>m;

    for(int i = 1; i <= m; i++){

        int x,y;

        cin>>x>>y;

        edge[x].push_back(Edge(y,i,0));

        edge[y].push_back(Edge(x,i,1));

        deg[x]++;

        deg[y]++;

    }

    int tmp = 0;

    int ans = 0;

    int sig = m;

    for(int i = 1; i <= n; i++){

        if( (deg[i]&1) && tmp == 0) tmp = i;

        else if( (deg[i]&1) && tmp != 0){

            edge[i].push_back(Edge(tmp,++sig,0));

            edge[tmp].push_back(Edge(i,sig,1));

            tmp = 0;

        }

        else ans++;

    }

    memset(c,-1,sizeof(c));

    for(int i = 1; i <= n; i++){

        if(vis[i] == 0){

            dfs(i);

        }

    }

    cout<<ans<<endl;

    for(int i = 1; i <= m; i++){

        cout<<c[i];

    }

    return 0;

}

1815 调查任务

基准时间限制：4 秒空间限制：524288 KB 分值: 80 难度：5级算法题

lbn是战忽中心——一个绝密的军事组织的一个军官，今天他接到了一个紧急任务：调查敌国X国某些城市的经济情况。

X国有N个城市，由M条单向道路连接，其中S城是X国的首都。

每个城市i有一个发达指数a[i]，我们定义城市i的经济状况为首都S到城市i任意一条路径上两个不同的城市x,y的a[x] mod a[y]的最大值。（x和y必须在同一条路径上，x，y可以是i或者S）

lbn当然能轻松地完成这个任务，但他想考考你。

样例解释：

首都为2

2到1只有一条路径，城市1的经济情况为a[2] mod a[1]=23

对于城市3的经济状况，我们可以选择路径2->4->3，并选择城市3 4，经济状况为a[3] mod a[4]=37，可以发现这是最大值。

对于城市4的经济状况，我们可以选择路径2->3->4，并选择城市3 4，经济状况为a[3] mod a[4]=37，可以发现这是最大值。

一个点可以被经过多次！

使用C++的选手请注意：

如果DFS爆栈请使用Visual C++编译，并在开头加上

数据已加强

Input

第一行四个正整数N,M,Q,S

分别表示X国城市数量，城市间有向边的数量，需要调查的城市的数目和首都的编号。每个城市的标号为1到N

第二行N个正整数，其中第i个整数表示a[i]。

第2至M+1行每行两个正整数x,y。表示有一条从城市x到y有向边。

第M+2行Q个正整数，表示需要调查的城市的数目的编号。

数据保证无重边无自环，不会查询首都。

1<=N,Q<=4*10^5

1<=M<=2*10^6

1<=a[i]<=10^9

Output

共一行Q个整数，按询问顺序输出每个城市的经济情况。

如果一个城市不存在任何一条从首都来的路径，则其经济情况输出-1。

Input示例

4 5 3 2

98 23 37 100

2 1

2 4

2 3

3 4

4 3

1 3 4

Output示例

23 37 37

题目解析

这题真的是吃了憋了，自己想的时候是对得，写得时候又忘了，后来去看网上大佬的代码，看了也是眼花，第二天起来脑子清醒了才终于调对了。废话不多说，进入主题。

意一条路径上两个不同的城市x,y的a[x] mod a[y]的最大值。（x和y必须在同一条路径上，x，y可以是i或者S） 咋一看题目又说加强数据，这里又说取模最大，看起来很复杂，其实一条路径上最大的a[x] mod a[y] 就是这条路径上的严格次大值，证明就不说了，很容易。然后Tarjan缩点后，在DAG图上面求就行了。

至于我一开始犯的错，就是记了一个某点的祖先最大，祖先次大，以为和自己次大，自己最大比一比就可以得到答案了，但是忽略了要在同一条路径上，所以wa了好久。后来想了想，大概有三种可能

ans1[i] 表示i所在路径上到i点的最大值

ans2[i] 表示i所在路径上到i点的次大值

fmx1[i] 表示i的所有祖先节点的最大值

fmx2[i] 表示i的所有祖先节点的次大值

然后我们在

ans1[u],ans2[u],mx1[v],mx2[v]

fmx1[i],mx1[i],mx2[i]

fmx2[i],mx1[i],mx2[i]

这三个中取得最大的ans2[v]（ans1[v]不一定最大，然后维护一下其他变量）

代码

1610 路径计数

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

路径上所有边权的最大公约数定义为一条路径的值。

给定一个有向无环图。

T次修改操作，每次修改一条边的边权，每次修改后输出有向无环图上路径的值为1的路径数量(对1,000,000,007取模)。

Input

第一行两个整数n和m，分别表示有向无环图上的点数和边数。（1<=n<=100，1<=m<=50,000）

第2~m+1行每行三个数x,y,z，表示有一条从x到y权值为z的边。(1<=x,y<=n，1<=z<=100)

第m+2行一个数T，表示修改操作次数(1<=T<=500)。

接下来T行每行两个数x,y,表示修改第x条边(按照读入的顺序)的边权为y(1<=x<=m,1<=y<=100)。

Output

T+1行，修改前和每次修改操作后输出答案。

Input示例

4 4

1 2 2

2 4 3

1 3 4

3 4 2

4

1 5

2 10

3 3

4 6

Output示例

1

1

0

1

0

题目解析

想了半天不会，去网上看了看大佬就懂了。由于gcd很小，第们很容易想到枚举，但是我们又无法去枚举gcd，其实换个思路，我们去枚举因子，去跑各个因子的路径数量，然后通过容斥就能够算出gcd了。修改的时候，只用考虑改前和改后的数字的因子就够了，其他因子不收影响。比如28->10（考虑1,2,4,7,14,28,5,10）这样就不用枚举所有因子，复杂度降了一个根号。

正解通过floyd和莫比乌斯函数获得答案

值为1的路径数量= ∑(1<=x<=100)值为x的倍数的路径数量∗u[x]，u[x] 为莫比乌斯函数。

值为x的倍数的路径数量可以把所有边权为x的倍数的边取出来计算路径条数。直接倒着容斥也可以求出gcd。

代码

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = 50010;

const int mod = 1e9+7;

int n,m,t;

int a[maxn],b[maxn],c[maxn];

long long dp[105];

long long mat[105][105][105];

int f[105],g[105];

long long dfs(int u,int d)

{

    if(dp[u]!=-1) return dp[u];

    long long ans=0;

    for(int i=1; i<=100; i++){

        if(mat[d][u][i]){

            ans+=(mat[d][u][i]+mat[d][u][i]*dfs(i,d))%mod;

        }

    }

    return dp[u]=ans;

}

long long cal(int u)

{

    CLR(dp,-1);

    for(int i=1; i<=100; i++){

        if(dp[i]==-1) dfs(i,u);

    }

    long long ans=0;

    for(int i=1; i<=100; i++){

        ans=(ans+dp[i])%mod;

    }

    return ans;

}

int main()

{

//    freopen("in.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=1; i<=m; i++){

        scanf("%d%d%d",&a[i],&b[i],&c[i]);

        for(int j=1; j*j<=c[i]; j++){

            if(c[i]%j==0){

                mat[j][a[i]][b[i]]++;

                if(c[i]/j!=j) mat[c[i]/j][a[i]][b[i]]++;

            }

        }

    }

    for(int i=1; i<=100; i++) f[i]=cal(i);

    for(int i=100; i>=1; i--){

        g[i]=f[i];

        for(int j=2*i; j<=100; j+=i){

            g[i]=(g[i]-g[j]+mod)%mod;

        }

    }

    printf("%d\n",g[1]);

    scanf("%d",&t);

    while(t--){

        int x,y;

        vector<int> v;

        scanf("%d%d",&x,&y);

        for(int i=1; i*i<=c[x]; i++){

            if(c[x]%i==0){

                mat[i][a[x]][b[x]]--,v.push_back(i);

                if(c[x]/i!=i) mat[c[x]/i][a[x]][b[x]]--,v.push_back(c[x]/i);

            }

        }

        c[x]=y;

        for(int i=1; i*i<=c[x]; i++){

            if(c[x]%i==0){

                mat[i][a[x]][b[x]]++,v.push_back(i);

                if(c[x]/i!=i) mat[c[x]/i][a[x]][b[x]]++,v.push_back(c[x]/i);

            }

        }

        for(int i=0; i<v.size(); i++) f[v[i]]=cal(v[i]);

        for(int i=100; i>=1; i--){

            g[i]=f[i];

            for(int j=2*i; j<=100; j+=i){

                g[i]=(g[i]-g[j]+mod)%mod;

            }

        }

        printf("%d\n",g[1]);

    }

    return 0;

}

1445 变色DNA

1445 变色DNA

题目来源： TopCoder

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

有一只特别的狼，它在每个夜晚会进行变色，研究发现它可以变成N种颜色之一，将这些颜色标号为0,1,2...N-1。研究发现这只狼的基因中存在一个变色矩阵，记为colormap，如果colormap[i][j]='Y'则这只狼可以在某一个夜晚从颜色i变成颜色j（一晚不可以变色多次），如果colormap[i][j]=‘N’则不能在一个晚上从i变成j色。进一步研究发现，这只狼每次变色并不是随机变的，它有一定策略，在每个夜晚，如果它没法改变它的颜色，那么它就不变色，如果存在可改变的颜色，那它变为标号尽可能小的颜色（可以变色时它一定变色，哪怕变完后颜色标号比现在的大）。现在这只狼是颜色0，你想让其变为颜色N-1，你有一项技术可以改变狼的一些基因，具体说你可以花费1的代价，将狼的变色矩阵中的某一个colormap[i][j]='Y'改变成colormap[i][j]='N'。问至少花费多少总代价改变狼的基因，让狼按它的变色策略可以从颜色0经过若干天的变色变成颜色N-1。如果一定不能变成N-1，则输出-1.

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5

每组测试数据有相同的结构构成：

每组数据第一行一个整数N,2<=N<=50。

之后有N行，每行N个字符，表示狼的变色矩阵，矩阵中只有‘Y’与‘N’两种字符，第i行第j列的字符就是colormap[i][j]。

Output

每组数据一行输出，即最小代价，无解时输出-1。

Input示例

3

3

NYN

YNY

NNN

8

NNNNNNNY

NNNNYYYY

YNNNNYYN

NNNNNYYY

YYYNNNNN

YNYNYNYN

NYNYNYNY

YYYYYYYN

6

NYYYYN

YNYYYN

YYNYYN

YYYNYN

YYYYNN

YYYYYN

Output示例

1

0

-1

题目解析

水题，对于矩阵的每一行，第一个可变基因花费0，第二个花费1，以此类推。。。

建图，求最短路就行了

代码

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<queue>

#include<stack>

#include<map>

#include<stdlib.h>

#include<set>

using namespace std;

#define CLR(a,b) memset(a,b,sizeof(a))

#define INF 0x3f3f3f3f

#define LL long long

#define Pi acos(-1.0)

#define EXP 1e-9

#define up(i,x,y) for(int i=x;i<=y;i++)

#define down(i,x,y) for(int i=x;i>=y;i--)

#define w(x) while(x)

#define Mod 1000000007

const int maxn = 60;

int edge[maxn][maxn];

int dis[maxn];

int vis[maxn];

int n;

void dijkstra()

{

    for(int i=1;i<n;i++)

        dis[i]=edge[0][i];

    dis[0]=0;

    vis[0]=1;

    for(int i=0;i<n;i++){

        int minn = INF;

        int k=0;

        for(int j=0;j<n;j++){

            if(!vis[j] && dis[j]<minn){

                minn=dis[k=j];

            }

        }

        vis[k]=1;

        for(int j=0;j<n;j++)

            if(!vis[j] && dis[j] > minn + edge[k][j])

                dis[j] = minn + edge[k][j];

    }

}

int main()

{

    int T;

    cin>>T;

    while(T--){

        CLR(edge,INF);

        CLR(dis,INF);

        CLR(vis,0);

        cin>>n;

        for(int i=0;i<n;i++){

            int ans=0;

            for(int j=0;j<n;j++){

                char x;

                cin>>x;

                if(x == 'Y')

                    edge[i][j]=ans++;

            }

        }

        dijkstra();

        if(dis[n-1]!=INF)

            cout<<dis[n-1]<<endl;

        else

            cout<<"-1"<<endl;

    }

    return 0;

}

1444 破坏道路

题目来源： CodeForces

基准时间限制：1.5 秒空间限制：131072 KB 分值: 80 难度：5级算法题

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

Input

单组测试数据。

第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n*(n-1)/2) )。

接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。

输入保证是一个连通图。

最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。

Output

输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。

Input示例

5 4

1 2

2 3

3 4

4 5

1 3 2

3 5 2

Output示例

0

题目解析

处理出所有点到所有点的最短路，然后直接枚举两个人都走过的路的首尾端点，注意一下不要漏情况就可以了。(有可能两人没走过同一条路，特判一下)

代码

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = 3010;

int vis[maxn];

int dis[maxn][maxn];

int x1,y1,l1,x2,y2,l2;

int t1,t2,t3;

struct Edge

{

    int from,to,next;

}edge[maxn*maxn/2];

int tol;

int head[maxn];

void init()

{

    tol = 0;

    CLR(head,-1);

}

void addedge(int u,int v)

{

    edge[tol].from = u;

    edge[tol].to = v;

    edge[tol].next = head[u];

    head[u] = tol++;

}

void bfs(int st)

{

    queue<int> Q;

    Q.push(st);

    CLR(vis,0);

    vis[st] = 1;

    while(Q.size()){

        int u = Q.front();

        Q.pop();

        for(int i = head[u]; i != -1; i = edge[i].next){

            int v = edge[i].to;

            if(vis[v]) continue;

            vis[v] = 1;

            dis[st][v] = dis[st][u] + 1;

            Q.push(v);

        }

    }

}

int main()

{

    init();

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i = 1; i <= m; i++){

        int u,v;

        scanf("%d%d",&u,&v);

        addedge(u,v);

        addedge(v,u);

    }

    scanf("%d%d%d",&x1,&y1,&l1);

    scanf("%d%d%d",&x2,&y2,&l2);

    for(int i = 1; i <= n; i++) bfs(i);

    int ans = 3010*3010;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j++){

            if(dis[x1][i] + dis[i][j] + dis[j][y1] <= l1 && dis[x2][i] + dis[i][j] + dis[j][y2] <= l2)

                ans = min(ans,dis[x1][i] + dis[i][j] + dis[j][y1] + dis[x2][i] + dis[j][y2]);

            if(dis[x1][i] + dis[i][j] + dis[j][y1] <= l1 && dis[x2][j] + dis[j][i] + dis[i][y2] <= l2)

                ans = min(ans,dis[x1][i] + dis[i][j] + dis[j][y1] + dis[x2][j] + dis[i][y2]);

        }

    }

    if(dis[x1][y1] <= l1 && dis[x2][y2] <= l2)

        ans = min(ans,dis[x1][y1] + dis[x2][y2]);

    if(ans == 3010*3010)

        printf("-1\n");

    else

        printf("%d",m-ans);

    return 0;

}

1076 2条不相交的路径

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边）

（注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路）

Input

第1行：2个数M N，中间用空格分开，M是顶点的数量，N是边的数量。（2 <= M <= 25000, 1 <= N <= 50000)

第2 - N + 1行，每行2个数，中间用空格分隔，分别是N条边的起点和终点的编号。例如2 4表示起点为2，终点为4，由于是无向图，所以从4到2也是可行的路径。

第N + 2行，一个数Q，表示后面将进行Q次查询。(1 <= Q <= 50000)

第N + 3 - N + 2 + Q行，每行2个数s, t，中间用空格分隔，表示查询的起点和终点。

Output

共Q行，如果从s到t存在2条不相交的路径则输出Yes，否则输出No。

Input示例

4 4

1 2

2 3

1 3

1 4

5

1 2

2 3

3 1

2 4

1 4

Output示例

Yes

Yes

Yes

No

No

题目解析

没什么好说的，tarjan求双联通分量。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn = 5e5 +10;

int dfn[maxn];

int low[maxn];

int Stack[maxn];

int vis[maxn];

int color[maxn];

int deep;

int top;

int sum;

int out[maxn];

vector<int>Edge[maxn];

void tarjan(int u,int from)

{

    dfn[u] = ++deep;

    low[u] = deep;

    vis[u] = 1;

    Stack[++top] = u;

    for(int i=0;i<Edge[u].size();i++){

        int v = Edge[u][i];

        if(from == v)

            continue;

        if(!dfn[v]){

            tarjan(v,u);

            low[u] = min(low[v],low[u]);

        }

        else{

            low[u] = min(low[v],low[u]);

        }

    }

    if(dfn[u] == low[u]){

        color[u] = ++sum;

        vis[u] = 0;

        while(Stack[top]!=u){

            color[Stack[top]] = sum;

            vis[Stack[top]] = 0;

            top--;

        }

        top--;

    }

}

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=m;i++){

        int x,y;

        cin>>x>>y;

        Edge[x].push_back(y);

        Edge[y].push_back(x);

    }

    for(int i=1;i<=n;i++){

        if(dfn[i] == 0) tarjan(i,-1);

    }

    int k;

    cin>>k;

    for(int i=0;i<k;i++){

        int x,y;

        cin>>x>>y;

        if(color[x] == color[y])

            cout<<"Yes"<<endl;

        else

            cout<<"No"<<endl;

    }

    return 0;

}

码农公寓

51nod图论题解（4级，5级算法题）

1805 小树

题目解析

1835 完全图

DP[i][j] = ∑(1<=k<=i-j+1)(C(k-1,i-1) * DP[k][1] * DP[i-k][j-1])###

DP[n][1] = 2^(n*(n+1)/2) - ∑(2<=i<=n)DP[n][i]

1967 路径定向

1815 调查任务

1610 路径计数

1445 变色DNA

1444 破坏道路

题目解析

代码

1076 2条不相交的路径

相关文章