zoj-Swordfish-2022-5-6

Graph model

zoj 1203

zoj1203
Find the shortest path .
As a plan .
Yes cross longitudinal sit mark x, y Axis

Minimum spanning tree

so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length.

kruskal Find the minimum spanning tree

//kruskal Find the minimum spanning tree 
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
using namespace std;
int f[110], n, m;
struct node
{
    
    int a, b;
    double c;
}t[5000];
int cmp(struct node x, struct node y)
{
    
    return x.c < y.c;
}
int find(int x)
{
    
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
double krus()
{
    
    int i, k = 0, x, y;
    double s=0;
    for (i = 1; i < m; i++) {
    
        x = find(t[i].a);
        y = find(t[i].b);
        if (x != y) {
    
            s += t[i].c;
            k++;
            if (k == n - 1)
                break;
            f[x] = y;
        }
    }
    return s;
}
int main()
{
    
    int i, j, k = 0;
    double s, x[110], y[110];
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    while (cin>>n) {
    
        if (n == 0)
            break;
        if (k >= 1)
            cout << endl;
        k++;
        for (i = 1; i <= n; i++) {
    
            cin >> x[i] >> y[i];
            f[i] = i;
        }
        m = 1;
        for (i = 1; i <= n; i++)
            for (j = 1; j < i; j++) {
    
                t[m].a = i;
                t[m].b = j;
                t[m++].c = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));       // Calculate the distance between two 
            }
        sort(t + 1, t + m, cmp);
        s = krus();
        printf("Case #%d:\nThe minimal distance is: %.2lf\n", k, s);
    }
    return 0;
}

zoj 2048

All highways can be used in both directions. Highways can freely cross each other.
but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the cost of building new highways.
Thus, the least expensive highway system will be the one that minimizes the total highways length.

Input

The input consists of two parts. The first part describes all towns in the country, and the second part describes all of the highways that have already been built.

The first line of the input contains a single integer N (1 <= N <= 750), representing the number of towns.
The next N lines each contain two integers, xi and yi separated by a space.
These values give the coordinates of ith town (for i from 1 to N).
Coordinates will have an absolute value no greater than 10000. Every town has a unique location.

The next line contains a single integer M (0 <= M <= 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.

Output

Write to the output a single line for each new highway that should be built in order to connect all towns with minimal possible total length of new highways. Each highway should be presented by printing town numbers that this highway connects, separated by a space.

If no new highways need to be built (all towns are already connected), then the output should be created but it should be empty.

Bordering , Make all points connected , Use the least highway length .

Sample Input

1

9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2

Sample Output

1 6
3 7
4 9
5 7
8 3

The road that has been repaired , The boundary right is 0, It's not fixed , The edge weight is the maximum .

use PointB Complete the function of searching sets and comparing weights

struct PointB  // A special space is responsible for recording the weights between endpoints 
{
    
	int parent;
	double price;
};

AC Code

#include<iostream>
#include<cmath>
using namespace std;
#define MAX_PRICE 1<<30
#define MAXN 1001
int f[1000];
struct node
{
    
	int x;
	int y;
	
}towns[750];

struct PointB  // A special space is responsible for recording the weights between endpoints 
{
    
	int parent;
	double price;
};

double map[MAXN][MAXN];
bool is_out;
PointB minimun[MAXN];      //parent Represents the parent node ,price Means the price 
int j = 0, ct = 0, i = 0, n = 0, m = 0;
bool used[MAXN];

int find(int x)
{
    
	if (x != f[x])
		f[x] = find(f[x]);
	return f[x];
}

void init()
{
    
	cin>>n;
	for (int i = 1; i <= n; i++) {
    
		cin >> towns[i].x>> towns[i].y;
		used[i] = false;
		minimun[i].price = MAX_PRICE;
	}

	for (int i = 1; i <= n; i++) {
    
		for (int j = 1; j <= n; j++) {
    
			map[i][j] = sqrt((towns[i].x - towns[j].x) * (towns[i].x - towns[j].x) + (towns[i].y - towns[j].y) * (towns[i].y - towns[j].y));
			map[j][i] = map[i][j];
		}
	}
	int m;
	cin >> m;
	int x, y;
	// For those already connected , A distance of 0
	for (int i = 0; i < m; i++) {
    
		cin >> x >> y;
		map[x][y] = 0;
		map[y][x] = 0;
	}

}
void prim()
{
    
	minimun[1].price = 0;
	used[1] = true;
	int now = 1;
	for (int i = 1; i < n; i++) {
    
		double min = MAX_PRICE;
		int next = 0;
		for (int j = 1; j <= n; j++) {
    
			if (!used[j]) {
    
				if (minimun[j].price > map[now][j]) 
				{
    
					minimun[j].price = map[now][j];
					minimun[j].parent = now;
				}
				if (min > minimun[j].price) {
    
					min = minimun[j].price;
					next = j;
				}
			}
		}
		// Output only when there is no connection 
		if (min != 0) {
    
			is_out = false;
			printf("%d %d\n", next, minimun[next].parent);
		}
		now = next;
		used[now] = true;
	}

}

int main()
{
    
	int t = 0;
	cin >> t;
	while (t--) {
    
			is_out = true;
			init();
			prim();
			if (t)
				printf("\n");
	}
	return 0;

}

A topological sort

There is the relationship between prerequisite courses and later courses .

AOV The Internet

Course examples

line up , You must row from high to low .

Homework ： zoj 2193

2193
Window Pains
Time Limit: 2000 msMemory Limit: 65536 KB

Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux’s windows would be represented by the following 2 x 2 windows:

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and then window 2 were brought to the foreground, the resulting representation would be:

. . . and so on . . .

Unfortunately, Boudreaux’s computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .
Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components:

Start line - A single line:

There are fixed some windows filled with numbers
We found the first and rightmost and top , The numbers of the four corners are 1,3,7,9 , unchanging

#include<stdio.h>
#include<string.h>
int main()
{
    
	int win[9][4][4];
	memset(win, 0, sizeof(win));
	int i, j, k, bi, bj;
	for (k = 0; k < 9; k++)
	{
    
		bi = k / 3;
		bj = k % 3;
		for (i = bi; i < bi + 2; i++)
			for (j = bj; j < bj + 2; j++)
				win[k][i][j] = k + 1;
	}
	int map[10][10], num;
	char s[11];
	while (gets(s), strcmp(s, "ENDOFINPUT"))
	{
    
		memset(map, 0, sizeof(map));
		for (i = 0; i < 4; i++)
			for (j = 0; j < 4; j++)
			{
    
				scanf("%d", &num);
				for (k = 0; k < 9; k++)
					if (win[k][i][j] && win[k][i][j] != num)
						map[num][win[k][i][j]] = 1;
			}
		for (k = 1; k <= 9; k++)
			for (i = 1; i <= 9; i++)
				for (j = 1; j <= 9; j++)
					map[i][j] = map[i][j] || (map[i][k] && map[k][j]);
		int flag = 1;
		for (i = 1; i <= 9; i++)
			for (j = 1; j <= 9; j++)
				if (map[i][j] && map[j][i])
					flag = 0;
		puts(flag ? "THESE WINDOWS ARE CLEAN" : "THESE WINDOWS ARE BROKEN");
		getchar();
		gets(s);
	}
	return 0;
}