The onlinejudge-problem-solving from wu-sunflower

onlinejudge-problem-solving's People

Contributors

Stargazers

Watchers

onlinejudge-problem-solving's Issues

2610 AOE网的关键路径

学长你好，我想问一下2610题目里你在判断好源点与汇点后，为什么在char里面存的是{1，0}而不是{start，0};
还有如果你有空的话，能帮我看看我的代码吗，我也是用dfs去算关键路径，万分感谢

#include<bits/stdc++.h>`
using namespace std;

const int MAX = 33;
int n, m;
int graph[MAX][MAX];//AOE图
int f[MAX];//判断是否到过此点
vector<int> v1;//记录当前路径
string str[10000];//关键路径字典化
int cnt;//当前关键路径组数
int maxx;//最大权值
int st, ed;//源点与汇点

void dfs(int pos, int sum) {
    if(pos == ed) {
        if(sum >= maxx) {
            if(sum > maxx) {
                for(int i = 0; i < cnt; i ++ )  str[i].erase();
                cnt = 0;
                maxx = sum;
            }
            for(int i = 0; i < v1.size(); i ++ ) str[cnt] += v1[i] + '0';
            cnt ++;
        }
        return;
    }

    for(int i = 1; i <= n; i ++ ) {
        if(f[i]) continue;
        if(graph[pos][i] != 0) {
            v1.push_back(i);
            f[i] = 1;
            dfs(i, sum + graph[pos][i]);
            f[i] = 0;
            v1.pop_back();
         }   
    }  
}

int main() {   
    while(scanf("%d %d", &n, &m) != EOF) {
        //初始化
        memset(graph, 0, sizeof(graph));
        for(int i = 0; i < cnt; i ++ )  str[i].erase();
        cnt = 0;
        maxx = 0;
		vector<int>().swap(v1);
		memset(f, 0, sizeof(f));
		
		
        int x, y, z;
        for(int i = 1; i <= m; i ++ ) {
            scanf("%d %d %d", &x, &y, &z);
            if(z > graph[x][y]) graph[x][y] = z;
        }
        for(int i = 1; i <= n; i ++ ) {
            bool gg = 1, hh = 1;
            for(int j = 1; j <= n; j ++ ) {
                if(i == j) continue;
                if(graph[i][j] != 0) gg = 0;
                if(graph[j][i] != 0) hh = 0;
            } 
            if(gg && !hh) ed = i;
            if(!gg && hh) st = i;
        } 
        v1.push_back(1);
        f[st] = 1;
        dfs(st, 0);
        if(cnt == 0) {printf("-1"); return 0;}
        sort(str, str + cnt);
        printf("%d\n", maxx);
        for(int i = 0; i < str[0].size() - 1; i ++ ) {
            printf("%c %c\n", str[0][i], str[0][i + 1]);
        }
    }
    return 0;
}

Recommend Projects