'C++'에 해당되는 글 10건

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

#define INT_MAX 2147483647
#define min(a,b) ((a>=b) ? b : a)

int main() {
	int N;
	int S, T, C;	// source, destination, # of connection
	int s, d, c;
	int ac[101][101];	// array of capacity
	int af[101][101];	// array of flow
	int ap[101];	// array of parent
	bool ab[101];	// array of black & white
	queue<int> q;	// queue for BFS
	int num = 1;
	
	while (true) {
		cin >> N;
		if (N == 0) break;
			
		memset(ac, 0x00, sizeof(ac));
		memset(af, 0x00, sizeof(af));
		
		cin >> S;	// source
		cin >> T;	// destination
		
		for (cin >> C; C; C--) {	// # of connections
			cin >> s;
			cin >> d;
			cin >> c;		
			
			ac[s][d] += c;
			ac[d][s] += c;
		}

		bool isPathExist = true;

		while (isPathExist) {
			memset(ap, 0x00, sizeof(ap));
			memset(ab, 0x00, sizeof(ab));

			while (!q.empty())
				q.pop();	// make it clear
			q.push(S);
			ab[S] = true;	// set it black
			ap[S] = 0;
			
			isPathExist = false;
			while(!q.empty()) {
				int cur = q.front();
				q.pop();
	
				if (cur == T) {
					isPathExist = true;	// we found it
					break;
				}
				for (int i = 1; i <= N; i++) {
					if (ab[i] == false && (ac[cur][i] - af[cur][i]) > 0) {
						// when it is white & residual capacity > 0 
						// (there exists a connection)
						q.push(i);
						ap[i] = cur;	// cur is the parent of i
						ab[i] = true;	// set it black
					}
				}	
			}
			
			if (isPathExist == true) {
				int cur = T;
				int min = INT_MAX;
				while (cur != 0) {
					int w = (ac[ap[cur]][cur]) - (af[ap[cur]][cur]);
					if (w != 0 && min > w)
						min = w;
					cur = ap[cur];				
				}
				cur = T;
				while (cur != 0) {
					if (ap[cur] != 0)
						af[ap[cur]][cur] += min;
					cur = ap[cur];				
				}
			} else {
				int sum = 0;
				for (int i = 1; i <= N; i++)
					sum += af[S][i];
				cout << "Network " << (num++) << endl;
				cout << "The bandwidth is " << sum << "." << endl << endl;
			}
		}
	}
	
	return 0;
}

먼저 기본적으로 세팅하는 부분이다. 특별한 것은 없다.

#include <iostream>

using namespace std; 

#define MAX_LENGTH_OF_PHONE_NUMBER 7
// 0, 1 are not translated into alphabets.
string numStr[8] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PRS", "TUV", "WXY"};

void printTelephoneWords(char*, char*, int);
void printTelephoneWordsNonRec(char*, char*);

int main() {
	char phone[MAX_LENGTH_OF_PHONE_NUMBER+1];	// original phone number
	char tphone[MAX_LENGTH_OF_PHONE_NUMBER+1]; // translated words

	while (true) {
		memset(tphone, 0x00, MAX_LENGTH_OF_PHONE_NUMBER+1);
		cin >> phone;
		if (cin.eof())
			break;
		cout << "With Recursion" << endl;
		printTelephoneWords(phone, tphone, 0);			
		
		cout << "With Iteration" << endl;
		printTelephoneWordsNonRec(phone, tphone);
	}
	
	return 0;
}

void printTelephoneWords(char *phone, char *tphone, int index) {
	if (index == strlen(phone)) {
		cout << tphone << endl;
		return;
	}

	for (int j = 0; j < 3; j++) {
		if (phone[index] == '0' || phone[index] == '1')
			tphone[index] = phone[index];
		else
			tphone[index] = numStr[phone[index]-'2'].at(j);	
		
		printTelephoneWords(phone, tphone, index+1);

		if (phone[index] == '0' || phone[index] == '1')
			return;
	}	
}

void printTelephoneWordsNonRec(char *phone, char *tphone) {
	int len = strlen(phone);
	
	for (int i = 0; i < len; i++) {
		if (phone[i] == '0' || phone[i] == '1') 
			tphone[i] = phone[i];
		else
			tphone[i] = numStr[phone[i]-'2'].at(0);
	}
		
	while (true) {
		cout << tphone << endl;

		for (int i = len - 1; i >= 0; i--) {
			if (tphone[i] == '0' || tphone[i] == '1') {
				tphone[i] = phone[i];
			} else if (tphone[i] == numStr[phone[i]-'2'].at(2)) {
				tphone[i] = numStr[phone[i]-'2'].at(0);
			} else if (tphone[i] == numStr[phone[i]-'2'].at(0)) {
				tphone[i] = numStr[phone[i]-'2'].at(1);
				break;
			} else if (tphone[i] == numStr[phone[i]-'2'].at(1)) {
				tphone[i] = numStr[phone[i]-'2'].at(2);
				break;
			}
			
			if (i == 0) return;
		}
	}	
}