头像

贴着土地生活


访客:554

离线:1天前



算法1

额外考虑了一些边界情况

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 10010;
typedef long long LL;

int n, m;
int dist1[N][N];
int dist2[N][N];
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
int p[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; 
}

int find(int a)
{
    if(p[a] != a) p[a] = find(p[a]);
    return p[a];
}

LL min(LL a, LL b)
{
    return a < b ? a : b;
}

struct Edge{
    int a, b;
    LL w;
    bool f;
    bool operator< (Edge &m) const
    {
        return w < m.w;
    }
}edges[M];

void dfs(int t, int fa, int maxv, int inf, int d1[], int d2[])
{
    d1[t] = maxv;
    d2[t] = inf;
    for(int i = h[t]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int nemaxv = maxv, neinf = inf;
        if(inf == -1 && maxv == -1) neinf = nemaxv = w[i];
        else if(w[i] > maxv) neinf = maxv, nemaxv = w[i];
        else if(w[i] < maxv && w[i] > inf) neinf = w[i];
        else if(maxv == inf && w[i] < inf) neinf = w[i];
        dfs(j, t, nemaxv, neinf, d1, d2);
    }
}

int main()
{
    cin >> n >> m;
    int x, y;
    LL z;
    for(int i = 0; i < m; ++ i)
    {
        cin >> x >> y >> z;
        edges[i] = {x, y, z, false};
    }
    sort(edges, edges + m);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++ i)
        p[i] = i;
    LL maxw = 0;
    for(int i = 0; i < m; ++ i)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            add(a, b, w);
            add(b, a, w);
            edges[i].f = true;
            maxw += w;
        }
    }

    for(int i = 1; i <= n; ++ i)
        dfs(i, -1, -1, -1, dist1[i], dist2[i]);

    LL res = 1e18;
    for(int i = 0; i < m; ++ i)
    {
        if(!edges[i].f)
        {
            LL t;
            bool flag = false;
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            if(w > dist1[a][b])
            {
                t = maxw + w - dist1[a][b];
                flag = true;
            }
            else if(w > dist2[a][b])
            {
                t = maxw + w - dist2[a][b];
                flag = true;
            }
            if(flag)    res = min(res, t);
        }
    }
    cout << res;
    return 0;
}



算法1 只建立黑边,求连通块数量和每个连通块内点的数量,就可以直接统计结果了,感觉最小生成树空间消耗会过大

时间复杂度 O(n)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010, M = 200100;
int n, m, t;
int e[M], ne[M], h[N], idx;
int st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int t)
{
    st[t] = true;
    int res = 1;
    for(int i = h[t]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
            res += dfs(j);
    }
    return res;
}

int main()
{
    cin >> t;
    for(int T = 1; T <= t; T ++)
    {
        cin >> n >> m;
        int x, y;
        memset(h, -1, sizeof h);
        memset(ne, 0, sizeof ne);
        memset(e, 0, sizeof e);
        memset(st, 0, sizeof st);
        idx = 0;
        for(int i = 0; i < m; ++ i)
        {
            cin >> x >> y;
            add(x, y);
            add(y, x);
        }
        int res = 0;
        int cnt = 0;
        for(int i = 1; i <= n; ++ i)
        {
            if(!st[i])
            {
                res += (dfs(i) - 1);
                cnt ++;
            }
        }
        res += ((cnt - 1) * 2);
        printf("Case #%d: %d\n", T, res);
    }
    return 0;
}




算法1

和最短路计数那题思路类似,只不过把宽搜换成dijkstra

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int, pair<int, int>> PIII;

const int N = 510;
const int M = 610;
int n, m, c1, c2;

int e[M * 2], ne[M * 2], h[N], w[M * 2], idx;
priority_queue<PIII, vector<PIII>, greater<PIII>> pq;
int dist[N];
int st[N];
int cnt[N];
int mem[N];
int mmem[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[c1] = 0;
    cnt[c1] = 1;
    pq.push({0, {c1, c1}});
    while(pq.size())
    {
        PIII t = pq.top();
        pq.pop();
        int d = t.x, p = t.y.x, pre = t.y.y;
        if(st[p])
        {
            if(d == dist[p])
            {
                cnt[p] += cnt[pre];
                mmem[p] = max(mmem[p], mmem[pre] + mem[p]);
            }
            continue;
        }
        st[p] = true;
        dist[p] = d;
        cnt[p] = cnt[pre];
        mmem[p] = mmem[pre] + mem[p];
        for(int i = h[p]; ~i; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
                pq.push({dist[p] + w[i], {j, p}});
        }
    }
}

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int main()
{
    cin >> n >> m >> c1 >> c2;
    for(int i = 0; i < n; ++ i)
        cin >> mem[i];
    memset(h, -1, sizeof h);
    int a, b, c;
    for(int i = 0; i < m; ++ i)
    {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra();
    printf("%d %d", cnt[c2], mmem[c2]);

}




算法1

朴素dijkstra,O(n2)
正向建图,反向建图,两次dijkstra

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1010, M = 100010;
int n, m, x;
vector<vector<int>> gc(1010, vector<int>(1010, 0x3f3f3f3f));
vector<vector<int>> go(1010, vector<int>(1010, 0x3f3f3f3f));
int distcome[N];
int distgo[N];
int st[N];

void dijkstra(int dist[], vector<vector<int> >& g)
{
    memset(st, 0, sizeof st);
    dist[x] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++ j)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = true;
        for(int j = 1; j <= n; ++ j)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
}

int main()
{
    cin >> n >> m >> x;
    int a, b, c;
    for(int i = 1; i <= m; ++ i)
    {
        cin >> a >> b >> c;
        gc[a][b] = min(gc[a][b], c);
        go[b][a] = min(go[b][a], c);
    }
    memset(distcome, 0x3f, sizeof distcome);
    dijkstra(distcome, gc);
    memset(distgo, 0x3f, sizeof distgo);
    dijkstra(distgo, go);
    int res = 0;
    for(int i = 1; i <= n; ++ i)
        if(i != x)
            res = max(res, distcome[i] + distgo[i]);
    cout << res;
    return 0;
}




题目链接 https://www.acwing.com/activity/content/problem/content/1505/1/

请问这样写为什么会TLE啊,是卡常数时间了码

错误的代码:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = 200010;
int e[M], ne[M], h[N], idx;
int n, m;
int listin[N];
int listout[N];
int dist[N];
int cnt[N];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs()
{
    int tt = -1, hh = 0;
    q[++ tt] = 1;
    cnt[1] = 1;
    listin[1] = true;
    while(hh <= tt)
    {
        int t = q[hh ++];
        listout[t] = true;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(!listin[j])
            {
                dist[j] = dist[t] + 1;
                cnt[j] += cnt[t];
                cnt[j] = cnt[j] % 100003;
                q[++ tt] = j;
                listin[j] = true;
            }
            else if(!listout[j] && dist[j] == dist[t] + 1)
            {
                    cnt[j] += cnt[t];
                    cnt[j] = cnt[j] % 100003;
            }
        }
    }

}


int main()
{
    cin >> n >> m;
    int x, y;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++ i)
    {
        cin >> x >> y;
        if(x != y)  
        {
         add(x, y);
         add(y, x);
        }
    }
    bfs();
    for(int i = 1; i <= n; ++ i)
        printf("%d\n", cnt[i]);
}



算法1

用极值剪枝, 可行性剪枝了, 还优化了搜索顺序, 但最后一个数据还是TLE, 哭辽, 蹲个大佬吧先

时间复杂度 ~~

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int map[N][N];
bool st[N][N];
int n, m;
int res = 0x3fff;
int h;
int idx[4] = {-1, 0, 1, 0}, idy[4] = {0, 1, 0, -1};
int vt[N][N];
bool cons[N][N];
int getmax()
{
    int maxv = 0;
    int idx  = 0;
    for(int i = 0; i < m * n; ++ i)
        if(!cons[i / m][i % m] && map[i / m][i % m] > maxv)
            {
                maxv = map[i / m][i % m];
                idx = i;
            }
    return idx;
}

void flood(int i, int j)
{
    vt[i][j] = true;   
    for(int k = 0; k < 4; ++ k)
    {
        int x = i + idx[k], y = j + idy[k];    
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(vt[x][y]) continue;
        if(st[x][y] != st[i][j]) continue;
        flood(x, y);
    }
}

bool check()
{
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(!vt[i][j])
            {
                flood(i, j);
                cnt ++;
            }
    if(cnt == 2)
        return true;
    return false;
}

void dfs(int sum, int cnt, int num, int left)
{
    if(sum > h) return;
    if(cnt >= res) return;
    if(left == 0) 
    {
        if(sum == h && check())
            res = cnt;
        memset(vt, 0, sizeof vt);
        return;
    }
    if(sum == h)
    {
        if(check())
           res = cnt;
        memset(vt, 0, sizeof vt);
        return;
    }
    cons[num / m][num % m] = true;
    st[num / m][num % m] = true;
    int maxidx = getmax();
    dfs(sum + map[num / m][num % m], cnt + 1, maxidx, left - 1);
    st[num / m][num % m] = false;
    dfs(sum, cnt, maxidx, left - 1);
    cons[num / m][num % m] = false;
}


int main()
{
    cin >> m >> n;
    int sum = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            {
                cin >> map[i][j];
                sum += map[i][j];
            }
    h = sum / 2;
    if(sum != h * 2)
        cout << 0;
    else
    {
        st[0][0] = true;
        cons[0][0] = true;
        dfs(map[0][0], 1, getmax(), m * n - 1);
        if(res != 0x3fff)
            cout << res;
        else
            cout << 0;
    }
    return 0;
}





这是一个有依赖的背包问题,加一个0学分的0好点把多棵树变成一棵然后改成选m+1门课即可

时间复杂度 O(MN)

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int M = 400;
const int N = 400;
int m, n;
int f[N][M];
int e[N], w[N], ne[N], h[N], idx;
void add(int a, int b, int c)
{
    ne[idx] = h[a]; h[a] = idx; e[idx] = b; w[b] = c; ++ idx;
}

void dfs(int u)
{
    for(int i = h[u]; ~i; i = ne[i]) 
    {
        dfs(e[i]);
        for(int j = m; j >= 0; -- j)
            for(int k = 0; k <= j; ++ k)
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);
    }
    for(int i = m + 1; i >= 1; -- i)
        f[u][i] = w[u] + f[u][i - 1];
    f[u][0] = 0;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++ i)
    {
        int a, c;
        cin >> a >> c;
        add(a, i, c);
    }
    dfs(0);
    printf("%d", f[0][m + 1]);
    return 0;
}



这是一个有依赖的背包问题,加一个0学分的0好点改成选m+1门课即可

时间复杂度 O(MN)

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int M = 400;
const int N = 400;
int m, n;
int f[N][M];
int e[N], w[N], ne[N], h[N], idx;
void add(int a, int b, int c)
{
    ne[idx] = h[a]; h[a] = idx; e[idx] = b; w[b] = c; ++ idx;
}

void dfs(int u)
{
    for(int i = h[u]; ~i; i = ne[i]) 
    {
        dfs(e[i]);
        for(int j = m; j >= 0; -- j)
            for(int k = 0; k <= j; ++ k)
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);
    }
    for(int i = m + 1; i >= 1; -- i)
        f[u][i] = w[u] + f[u][i - 1];
    f[u][0] = 0;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++ i)
    {
        int a, c;
        cin >> a >> c;
        add(a, i, c);
    }
    dfs(0);
    printf("%d", f[0][m + 1]);
    return 0;
}



include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int mod = 1e9 + 7;
int w[60][60];
int f[60][60][15][15];
int mark[60][60][15][15];
int n, m, k;
int func(int i, int j, int k, int v)
{
if((i > n) || (j > m)) return 0;
if(mark[i][j][k][v]) return f[i][j][k][v];
if((i == n) && (j == m))
{
mark[i][j][k][v] = 1;
if(((k == 1) && (v < w[i][j])) || (k == 0))
{
f[i][j][k][v] = 1;
printf(“f[%d][%d][%d][%d]: %d\n”,i,j,k,v,f[i][j][k][v]);
return f[i][j][k][v];
}
else
{
f[i][j][k][v] = 0;
printf(“f[%d][%d][%d][%d]: %d\n”,i,j,k,v,f[i][j][k][v]);
return f[i][j][k][v] = 0;
}
}
f[i][j][k][v] = (func(i + 1, j, k, v) + func(i, j + 1, k, v)) % mod ;
if((k > 0) && (v < w[i][j]))
f[i][j][k][v] = f[i][j][k][v] + (func(i + 1, j, k - 1, w[i][j]) + func(i, j + 1, k - 1, w[i][j])) % mod;
mark[i][j][k][v] = 1;
printf(“f[%d][%d][%d][%d]: %d\n”,i,j,k,v,f[i][j][k][v]);
return f[i][j][k][v] % mod;
}

int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i)
for(int j = 1; j <= m;
j)
cin >> w[i][j];
int res = func(1, 1, k, 0);
cout << res;
return 0;
}




题目链接1212 地宫取宝

求大佬帮忙看下bug在哪里(哭)。

错误的代码:

#include <iostream>
#include <cstring>
using namespace std;

int mod = 1e9 + 7;
int w[60][60];
int f[60][60][15][15];//f[i][j][k][v] 表示从(i, j)到(m, n)取k件物品且此时已取物品最大价值为v的方案数
int mark[60][60][15][15];
int n, m, k;
int func(int i, int j, int k, int v)
{
    if((i > n) || (j > m)) return 0;
    if(mark[i][j][k][v]) return f[i][j][k][v];
    if((i == n) && (j == m))
    {
        mark[i][j][k][v] = 1;
        if(((k == 1) && (v < w[i][j])) || (k == 0))
            return f[i][j][k][v] = 1;
        else 
            return f[i][j][k][v] = 0;
    }
    f[i][j][k][v] = (func(i + 1, j, k, v) + func(i, j + 1, k, v)) % mod ;
    if((k > 0) && (v < w[i][j]))
        f[i][j][k][v] = f[i][j][k][v] + (func(i + 1, j, k - 1, w[i][j]) + func(i, j + 1, k - 1, w[i][j])) % mod;
    mark[i][j][k][v] = 1;
    return f[i][j][k][v] % mod;
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            cin >> w[i][j];
    int res = func(1, 1, k, 0);
    cout << res;
    return 0;
}

编译器报了什么错误?Compile Error? Runtime Error?