# Untitled

unknown
plain_text
a month ago
6.7 kB
1
Indexable
Never
```ThanhTri, Frog, Farm, wellprj
//TanCongThanhTri
#include<iostream>

using namespace std;
#define SIZE 100
int N, answer, root;
int lienket[100][100] = {0};
int trongluong[100] = {0};
int visited[100] = {0};
int parent[100] = {0};
void clear_visit() {
for(int i = 0; i < N; i++) {
visited[i] = 0;
}
}
int DFS(int k, int cha) {
visited[k] = 1;
parent[k] = cha;
for(int i = 0; i < N; i++) {
if(lienket[k][i]) { //ton tai khoang k->i
if(!visited[i]) {
if(DFS(i, k)) {
return 1;
}
} else { //neu vi tri da visited va ko phai cha cua dinh hien tai. khi do se co 1 chu trinh
if(i != cha && cha != -1 && i == root) {
int sum = trongluong[k] + trongluong[i];
int minValue = sum;
int vStart = k;
int vEnd = i;
//tim canh be nhat trong chu trinh
int x = k;
while(parent[x] != -1) {
sum = trongluong[x] + trongluong[parent[x]];
if(sum < minValue) {
minValue = sum;
vStart = parent[x];
vEnd = x;
}
x = parent[x];
}
lienket[vStart][vEnd] = lienket[vEnd][vStart] = 0; //bo canh nho nhat trong chu trinh
return 1;
}
}
}
}
return 0;
}
int TC;
int main() {
//freopen("Text.txt","r", stdin);
int TC, idx, tmp, C;
cin >> TC;
for(int tc = 1; tc <= TC; tc++) {
cin >> N;
//reset
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
lienket[i][j] = 0;
}
}
//input data
for(int i = 0; i < N; i++) {
cin >> idx;
cin >> trongluong[idx] >> C;
for(int j = 0; j < C; j++) {
cin >> tmp;
lienket[idx][tmp] = 1;
lienket[tmp][idx] = 1;
}
}
for(int i = 0; i < N; i++) {
clear_visit();
root = i;
if(DFS(i, -1)) i--;
}
cout << answer << endl;
}
return 0;
}

//TheFrog
#include<iostream>

using namespace std;
int tc, n, inf = 1000000000, lowE = 1, highE = 200;
int r[3][201], a[201][201];
int sqrtt(int x) {
int i = 0;
while(i * i < x) {
i++;
}
return i;
}
int energyJump(int x1, int y1, int r1, int x2, int y2, int r2) {
int e = sqrtt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) - r1 - r2;
if(e <= 40) return lowE;
else if(e <= 90) return highE;
else return inf;
}
int findMinE() {
bool selected[201] = {
0
};
int selectedCnt = 0;
int minEn[201];
minEn[0] = 0;
for(int i = 1; i < n; i++) {
minEn[i] = inf;
}
int nearestLeaf = 0, nearestDist; //id và kho?ng cách c?a chi?c lá g?n nh?t
while(selectedCnt < n) { //l?p cho đ?n khi t?t c? lá đ? đư?c ch?n
//trong s? lá chưa ch?n, t?m cái có kho?ng cách g?n nh?t (tham lam)
nearestDist = inf;
for(int i = 0; i < n; i++) {
if(!selected[i] && minEn[i] < nearestDist) {
nearestDist = minEn[i];
nearestLeaf = i;
}
}
//Đi?u ki?n d?ng: lá đang thăm có kho?ng cách là INF, ho?c đ? g?p đư?c lá th? N - 1 (đích)
if(nearestDist == inf || nearestLeaf == n - 1) break;
//Đánh d?u thăm
selectedCnt++;
selected[nearestLeaf] = true;
//C?p nh?t kho?ng cách c?a các lá có th? nh?y t?i t? lá đang thăm
for(int i = 0; i < n; i++)
if(!selected[i] && minEn[nearestLeaf] + a[nearestLeaf][i] < minEn[i]) minEn[i] = minEn[nearestLeaf] + a[nearestLeaf][i];
}
return minEn[n - 1];
}
int main() {
freopen("input.txt", "r", stdin);
cin >> tc;
for(int t = 1; t <= tc; t++) {
cin >> n;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(j == i) a[i][j] = 0;
else a[i][j] = inf;
}
}
for(int i = 0; i < n; i++) {
cin >> r[0][i] >> r[1][i] >> r[2][i];
for(int j = 0; j < i; j++) {
a[i][j] = a[j][i] = energyJump(r[0][i], r[1][i], r[2][i], r[0][j], r[1][j], r[2][j]);
}
}
int minE = findMinE();
if(minE == inf) cout << -1 << endl;
else cout << minE / highE << " " << minE % highE << endl;
}
return 0;
}

//BaoVeNongTrang
#include<iostream>
using namespace std;

const int MAX = 705;

int N,M; // L?n lư?t là s? lư?ng hàng, c?t c?a ma tr?n
int Answer; // K?t qu? là s? lư?ng đ?nh đ?i
int Map[MAX][MAX]; // B?n đ? c?a nông trang

bool Visit[MAX][MAX]; // Đánh d?u đ? ki?m tra đ? duy?t hay chưa
bool IsHill; // Đánh d?u xem có ph?i là đ?nh đ?i hay không

int drow[8] = {-1,-1,-1, 0,0, 1,1,1};
int dcol[8] = {-1, 0, 1,-1,1,-1,0,1};

void DFS(int row, int col)
{
// T?i m?i đi?m ta s? đánh d?u đi?m đó đ? đư?c duy?t
Visit[row][col] = true;

for(int i = 0; i < 8; i++)
{
int r = row + drow[i];
int c = col + dcol[i];

if(r >= 0 && r < N && c >= 0 && c < M)
{
// T?i m?t đi?m mà t?n t?i 1 đi?m k? có giá tr? l?n hơn
// th? đi?m đó không ph?i đ?nh đ?i
if(IsHill && Map[r][c] > Map[row][col]) IsHill = false;

// Duy?t t?i các đi?m có cùng đ? cao mà chưa đư?c duy?t
// v? các đi?m đó s? thu?c cùng 1 đ?nh đ?i.
if(Map[r][c] == Map[row][col] && !Visit[r][c]) DFS(r, c);
}
}
}

int main()
{
//freopen("input.txt","r",stdin);
ios::sync_with_stdio(false);

// Nh?p đ?u vào
cin >> N >> M;
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
{
cin >> Map[i][j];
Visit[i][j] = false;
}

// Duy?t t?ng ph?n t? trong ma tr?n
// và ki?m tra t?i ph?n t? chưa đư?c xét
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
if(!Visit[i][j])
{
// Kh?i t?o IsHill = true, sau đó s? d?ng thu?t toán DFS
// đ? duy?t ma tr?n. Sau quá tr?nh duy?t, n?u như IsHill v?n có
// giá tr? true th? ch?ng t? đi?m v?a xét là đ?nh đ?i.
IsHill = true;
DFS(i, j);
}

// In k?t qu? s? đ?nh đ?i
cout << Answer << endl;

return 0;
}

//welProject
#define _CRT_SECURE_NO_WARNINGS
#define SIZE 109#include<iostream>

using namespace std;
int visit[SIZE];
int A[SIZE][SIZE];
int countdown;
int i, j;
int mini;
int jmini;
int main(int argc, char ** argv) {
int test_case;
int T, N;
ios::sync_with_stdio(false);
//freopen("Well Project.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case) {
cin >> N;
for(i = 1; i <= N; i++) {
for(j = 1; j <= N; j++) {
cin >> A[i][j];
}
visit[i] = 0;
}
// PRIM
// Add 1st vertex to MST
visit[1] = 1;
countdown = 1;
//Add one by one vertex to MST
while(countdown < N) {
//Find the minimum weight vertex
mini = 1000000;
for(i = 1; i <= N; i++) {
if(visit[i] == 1) {
for(j = 1; j <= N; j++) {
if(j != i && visit[j] == 0) {
if(A[i][j] < mini) {
mini = A[i][j];
jmini = j;
}
}
}
}
}
visit[jmini] = 1;