글 읽기 - 최대유량 초보자..

didwlvv 6년 전 0

최대유량으로 짰는데 이게 소문자 대문자가 구별이 된다고 하니까 그냥 문자로 받아서 아스키 값으로 들어가게했습니다. 근데 안돌아가네요.. 알려주시면 감사하겠습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
vector<int>v[30];
int n,sink,source;  int capacity[130][130];   int flow[130][130];   int p[130];
void init();    void solve();

int main(){
    init();
    solve();
    return 0;
}

void init(){
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++){
        char a,b;   int c;
        scanf(" %c %c %d", &a,&b,&c);
        
        v[a].push_back(b);
        v[b].push_back(a);
        capacity[a][b]=c;
    }
    
    
    
}

void solve(){
    int res=0;
    sink ='Z';
    
    while(1){
        queue<int>q;
        memset(p,-1,sizeof p);
        p['A']=0;
        char t='A';
        q.push(t);
        
        while(!q.empty() && p[sink]==-1){
            int now =q.front();
            q.pop();
            
            for(int i=0; i<v[now].size(); i++){
                int next =v[now][i];
                
                if(capacity[now][next] - flow[now][next] >0 && p[next]==-1){
                    p[next]=now;
                    q.push(next);
                }
            }
        }
        
        if(p[sink]==-1)break;
        int amount=0x3f3f3f3f;
        
        for(int i=sink; i !=source; i=p[i]){
            amount = min(amount, capacity[p[i]][i] - flow[p[i]][i]);
        }
        
        for(int i=sink; i !=source; i=p[i]){
            flow[p[i]][i] +=amount;
            flow[i][p[i]] -=amount;
        }
        
        res +=amount;
    }
    
    cout << res<<endl;
}

wonmo 6년 전 2

아래 코드로AC 받았습니다.

바뀐점은 8행 v의 배열을 130으로 증가시킨 것,

27행 A에서 B로 가는 경로가 2개 이상 있을 수 있으므로 +=연산을 한것,

37행 source또한 0이 아닌 'A'로 초기화 했습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
vector<int>v[130];
int n, sink, source;  int capacity[130][130];   int flow[130][130];   int p[130];
void init();    void solve();

int main() {
	init();
	solve();
	return 0;
}

void init() {
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		char a, b;   int c;
		scanf(" %c %c %d", &a, &b, &c);

		v[a].push_back(b);
		v[b].push_back(a);
		capacity[a][b] += c;
	}



}

void solve() {
	int res = 0;
	sink = 'Z';
	source = 'A';
	while (1) {
		queue<int>q;
		memset(p, -1, sizeof p);
		p['A'] = 0;
		char t = 'A';
		q.push(t);

		while (!q.empty() && p[sink] == -1) {
			int now = q.front();
			q.pop();

			for (int i = 0; i<v[now].size(); i++) {
				int next = v[now][i];

				if (capacity[now][next] - flow[now][next] >0 && p[next] == -1) {
					p[next] = now;
					q.push(next);
				}
			}
		}

		if (p[sink] == -1)break;
		int amount = 0x3f3f3f3f;

		for (int i = sink; i != source; i = p[i]) {
			amount = min(amount, capacity[p[i]][i] - flow[p[i]][i]);
		}

		for (int i = sink; i != source; i = p[i]) {
			flow[p[i]][i] += amount;
			flow[i][p[i]] -= amount;
		}

		res += amount;
	}

	cout << res << endl;
}

didwlvv 6년 전 0

감사합니다. 저도 생각을 해봤는데 파이프가 두번 올 수 있다는 생각은 아예 못했네요ㅎㅎ

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

문제

문제

출처

ICPC

최대유량 초보자..

didwlvv 6년 전 0

wonmo 6년 전 2

didwlvv 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말