Untitled

#include <iostream>
using namespace std;

int N,linh_kien[21];
int voucher,so_luong,giam_gia[31][21];
int mua,TT[21];
int gia,visit[21];
int a,gia_cho_troi;
int result = 10000000;
int count1[21];
int TG = 0 ;

void backtrack (int vt){
	if(vt == voucher){
		int gia_cho_troi = 0;
		for(int i = 1; i <=  mua; i++){
			if(visit[TT[i]] == 0){
				gia_cho_troi += linh_kien[TT[i]];
			}
		}
		if(TG + gia_cho_troi < result) result = TG + gia_cho_troi;
		return;
	}
	for(int i= 0; i< 2; i++){
		if(i == 0 ) backtrack(vt+1);
		else{
			for(int j = 1; j <= giam_gia[vt][2];j++){
				visit[giam_gia[vt][j+2]] ++;
			}
			TG += giam_gia[vt][1];
			if(result > TG) backtrack(vt+1);
			TG -= giam_gia[vt][1];
			for(int j = 1; j <= giam_gia[vt][2];j++){
				visit[giam_gia[vt][i+2]] --;
			}
		}
	}
}

int main(){
	freopen ("Text.txt","r",stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc ++){
		cin >> N;
		for(int i = 1; i <= N; i++){
			cin >> linh_kien[i];
			visit[i] = 0;
		}
		cin >> voucher ;
		for(int i = 1; i <= voucher;i++){
			count1[i] = 0;
			cin >> giam_gia[i][1] >> giam_gia[i][2];
			for(int j = 1; j <= giam_gia[i][2] ; j++){
				cin >> giam_gia[i][j+2];
			}
		}
		cin >> mua;
		for(int i = 1; i <= mua;i++){
			cin >> TT[i];
		}
		result = 1000000 ;
		TG = 0;
		backtrack(0);
		cout << "#" << tc << " " << result << endl;
	}
	return 0;
}



 minimal
#include<iostream>
using namespace std;

int main()
{
	int test_case;
	int T, k, n;
	int arr[100000];

	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> k >> n;
		int sum1 = 0;
		for(int i = 0; i < n; i++) {
			cin >> arr[i];
			
		}
		int max = 0;
		for(int i = 0; i < n; i++) {
			if(arr[i] > max) {
				max = arr[i];
			}
		}
		
		while(true) {
			
			int sum = 0;
			int cnt = 0;
			for(int i = 0; i < n; i++) {
				sum += arr[i];
				if (sum>max) {
					cnt++;
					sum = arr[i];
				}				
			}
			if(cnt < k) {
				break;
			} else {
				max++;
			}
		}
		cout << "#" << test_case << " " << max << endl;
	}
	return 0;
}



/*#include<iostream>
using namespace std;

int main()
{
	int test_case;
	int T, k, n;
	int arr[100000];

	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> k >> n;
		int sum1 = 0;
		for(int i = 0; i < n; i++) {
			cin >> arr[i];
			sum1 += arr[i];
		}
		int max = 0;
		for(int i = 0; i < n; i++) {
			if(arr[i] > max) {
				max = arr[i];
			}
		}
		int check = (sum1 + max) / 2;
		while(true) {
			if (sum1 <= max) {break;}
			int sum = 0;
			int cnt = 0;
			for(int i = 0; i < n; i++) {	
				sum += arr[i];
				if(sum > check) {
					cnt++;
					sum = arr[i];
				}
			}
			if(cnt < k) {
				sum1 = check;
				check = (sum1 + max) / 2;
			} else {
				max = check + 1;
				check = (sum1 + max) / 2;
			}
		}
		cout << "#" << test_case << " " << check << endl;
	}
	return 0;
}*/

hugo dao vang
#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int qx[1000], qy[1000], f = -1, r = -1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void Push(int x, int y) {
	r++;
	qx[r] = x;
	qy[r] = y;
}

void Pop(int& x, int& y) {
	f++;
	x = qx[f];
	y = qy[f];
}
void Reset() {
	f = r = -1;
}
bool isEmpty() {
	return f == r;
}

int n, m, g;
int map[50][50];
int visit[50][50];
int gm[101][3];
int kq[101][3];
int minPath,maxGm,curGm,curPath;
void saveKq() {
	for (int i = 1; i <= g; i++) {
		kq[i][0] = gm[i][0];
		kq[i][1] = gm[i][1];
		kq[i][2] = gm[i][2];
	}
}

void setVisitGm(int x, int y) {
	for (int i = 1; i <= g; i++) {
		if (x == gm[i][0] && y == gm[i][1]) {
			gm[i][2] = 1;
			break;
		}
	}
}
void resetVisit() {
	for (int i = 1; i <= g; i++) gm[i][2] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = -1;
		}
	}
}

void bfs(int r, int c) {
	Reset();
	Push(r, c);
	visit[r][c] = 0;
	curGm = 0;
	curPath = 0;
	while (!isEmpty()) {
		int x, y;
		Pop(x, y);
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && visit[xx][yy] == -1 && map[xx][yy]!=0) {
				Push(xx, yy);
				visit[xx][yy] = visit[x][y] + 1;
				if (map[xx][yy] == 2) {
					curGm++;
					setVisitGm(xx, yy);
					curPath = max(curPath, visit[xx][yy]);
				}
			}
		}
	}
}
int main() {
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;

	for (int t = 1; t <= T; t++) {
		cin >> n >> g;
		for (int i = 1; i <= g; i++) {
			cin >> gm[i][0] >> gm[i][1];
			gm[i][2] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> map[i][j];
			}
		}
		for (int i = 1; i <= g; i++) {
			map[gm[i][0]][gm[i][1]] = 2;
		}
		maxGm = 0;
		minPath = 1e9;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == 1) {
					resetVisit();
					bfs(i, j);
					if (curGm > maxGm) {
						maxGm = curGm;
						minPath = curPath;
						saveKq();
					}
					else if (curGm == maxGm && curPath != 0) {
						if (curPath < minPath) {
							minPath = curPath;
							saveKq();
						}
					}
				}
			}
		}
		cout << "Case #" << t << endl;
		if (minPath == 1e9) {
			cout << -1 << endl;
		}
		else {
			cout << minPath << endl;
			for (int i = 1; i <= g; i++) {
				if (kq[i][2] == 0) {
					cout << kq[i][0] << " " << kq[i][1] << endl;
				}
			}
		}
	}

	return 0;
}

tan cong thanh tri 
#include <iostream>
using namespace std;
int n,thanh,so_may_bd,thanh_lk;
int array[110][110];
int dinh[110],ban_da[110],flag;
int result;

void DFS(int temthanh,int thanh, int sl, int min, int d1, int d2){
	if(temthanh == thanh && sl >= 3){
		flag = 1;
		result += min;
		array[d1][d2] = 0;
		array[d2][d1] = 0;
		return;
	}
	for(int i = 0; i < n; i++){
		if(flag == 1) return;
		if(array[temthanh][i] == 1 && (dinh[i] == 0 || (i == thanh && sl >= 3))){
			dinh[i] = 1;
			int value = ban_da[temthanh] + ban_da[i];
			if(min > value){
				DFS(i,thanh,sl+1,value,temthanh,i);
			}
			else DFS(i,thanh,sl+1,min,d1,d2);
		}
	}
}

int main (){
	freopen ("Text.txt","r",stdin);
	int T; cin >> T;
	for(int tc = 1 ; tc <= T; tc++){
		cin >> n;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				array[i][j] = 0;
				dinh[j] = 0;
			}
		}
		for(int i = 0; i < n; i ++){
			cin >> thanh >> so_may_bd >> thanh_lk;
			ban_da[thanh] = so_may_bd;
			for(int j = 0; j < thanh_lk; j++){
				int c;
				cin >> c;
				array[thanh][c] = 1;
				array[c][thanh] = 1;
			}
		}
		result = 0;
		for(int i = 0; i < n ; i++){
			for(int j = 0; j < n; j++){
				dinh[j] = 0;
			}
			dinh[i] = 1;
			flag = 0;
			DFS(i,i,1,1000000,-1,-1);
		}
		cout << result << endl;
	}
	return 0;
}