글 읽기 - 넽웤 유량문제 질문

sgc109 7년 전 1

단순한 유량문제라고 생각해서 에드몬드카프로 작성해봤는데 WA가 나오는데.. 혹시 여기에 일반적인 플로우문제와 다르게 추가적으로 고려해줘야 하는 것이 있나요?

	#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <set>
// #include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

using namespace std;

typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;

const int INF = 0x3a3a3a3a;
const long long INFL = 0x3a3a3a3a3a3a3a3a;
const int MAX_N = 1000000;
int n;

vi adj[220];
int cap[220][220],flow[220][220];
int parent[220];

int edmonds(int start, int finish) {
	int ret = 0;

	while(true) {
		queue<int> q;
		q.push(start);
		memset(parent,-1,sizeof(parent));
		parent[start]=start;
		while(!q.empty() && parent[finish] == -1) {
			int here = q.front();
			q.pop();
			for(auto &there : adj[here]) {
				if(cap[here][there]-flow[here][there]>0 && parent[there] == -1) {
					parent[there] = here;
					q.push(there);
				}
			}
		}

		if(parent[finish] == -1) break;

		int minFlow=INF;
		for(int p = finish; p != parent[p]; p = parent[p]) {
			minFlow = min(minFlow, cap[parent[p]][p]-flow[parent[p]][p]);
		}
		for(int p = finish; p != parent[p]; p = parent[p]) {
			flow[parent[p]][p] += minFlow;
			flow[p][parent[p]] -= minFlow;
		}
		ret += minFlow;
	}
	return ret;
}
int main() {
	inp1(n);
	FOR(i,n) {
		char a,b;
		int c;
		scanf(" %c %c %d",&a,&b,&c);
		cap[a-'A'][b-'A']=c;
		adj[a-'A'].pb(b-'A');
		adj[b-'A'].pb(a-'A');
	}
	printf("%d",edmonds('A'-'A','Z'-'A'));

	return 0;
}

plzrun 7년 전 0

이거 소문자도 있어요 ㅎ

plzrun 7년 전 0

음 다시보니까.. 배열 크기 많이 잡은게 저렇게 빼도 소문자가 고려되나보네염?

근데 자세히보니까
61, 64번째 줄에 p!=parent[p]라고 되어있는데 이거 p!=start여야 하는거 아닌가요?

plzrun 7년 전 0

아니다.. 직접 바꿔보고 말씀드릴게용 ㅋ

plzrun 7년 전 2

78번째 줄만 +=c로 바꿔주시면 됩니다 ㅎ

다른건 체크해보니 이상이 없군요...

인접행렬만 깔끔하게 한번만 push_back하는것도 괜찮을 것 같아요 ㅎ

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <set>
// #include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
 
using namespace std;
 
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;
 
const int INF = 0x3a3a3a3a;
const long long INFL = 0x3a3a3a3a3a3a3a3a;
const int MAX_N = 1000000;
int n;
 
vi adj[220];
int cap[220][220],flow[220][220];
int parent[220];
 
int edmonds(int start, int finish) {
    int ret = 0;
 
    while(true) {
        queue<int> q;
        q.push(start);
        memset(parent,-1,sizeof(parent));
        parent[start]=start;
        while(!q.empty() && parent[finish] == -1) {
            int here = q.front();
            q.pop();
            for(auto &there : adj[here]) {
                if(cap[here][there]-flow[here][there]>0 && parent[there] == -1) {
                    parent[there] = here;
                    q.push(there);
                }
            }
        }
 
        if(parent[finish] == -1) break;
 
        int minFlow=INF;
        for(int p = finish; p != parent[p]; p = parent[p]) {
            minFlow = min(minFlow, cap[parent[p]][p]-flow[parent[p]][p]);
        }
        for(int p = finish; p != parent[p]; p = parent[p]) {
            flow[parent[p]][p] += minFlow;
            flow[p][parent[p]] -= minFlow;
        }
        ret += minFlow;
    }
    return ret;
}
int main() {
    inp1(n);
    FOR(i,n) {
        char a,b;
        int c;
        scanf(" %c %c %d",&a,&b,&c);
        cap[a-'A'][b-'A']+=c;
        adj[a-'A'].pb(b-'A');
        adj[b-'A'].pb(a-'A');
    }
    printf("%d",edmonds('A'-'A','Z'-'A'));
 
    return 0;
}

moonsoo5522 7년 전 0

감사합니다 도움이 많이 되었습니다 ^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

넽웤 유량문제 질문

sgc109 7년 전 1

plzrun 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 2

moonsoo5522 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말