首页 > 其他 > 详细

洛谷2747(不相交路线、dp)

时间:2019-06-07 16:40:42      阅读:108      评论:0      收藏:0      [点我收藏+]

要点

  • 反思:以前是在紫书上做过的……
  • \(dp[i][j]\)是从1引两条路到达i、j的最大值
  • 为了不相交,则\(dp[i][i]\)都是非法的,不转移它,也不用它转移
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

const int maxn = 105, inf = 0x3f3f3f3f;
int n, m, ans = 1;
int adj[maxn][maxn], dp[maxn][maxn];
map<string, int> mp;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        mp[s] = i;
    }
    for (int i = 1; i <= m; i++) {//graph
        string s, t;
        cin >> s >> t;
        int u = mp[s], v = mp[t];
        adj[u][v] = adj[v][u] = 1;
    }

    dp[1][1] = 1;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)//i < j: not intersect
            for (int k = 1; k < j; k++)
                if (adj[k][j] && dp[i][k])
                    dp[i][j] = dp[j][i] = max(dp[i][j], dp[i][k] + 1);
                
    for (int i = 1; i < n; i++)
        if (adj[i][n])
            ans = max(ans, dp[i][n]);
    return !printf("%d\n", ans);
}

洛谷2747(不相交路线、dp)

原文:https://www.cnblogs.com/AlphaWA/p/10988404.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!