Участник:Easik/DISJPATH

Материал из DISCOPAL
Перейти к: навигация, поиск

Почему-то форматирование кода слетает после копирования с Visual Studio или из поля редактирования в системе соревнований. Но я проверил, что при копировании кода с этой страницей он проходит все тесты на системе соревнований.

C \ gcc

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> /* bool */
#include <assert.h>  /* assert() */
 
#define INF             (int)1e9
#define MAX_EDGES       (int)2e5
#define MAX_VERTICES    (int)1e4
#define QUEUE_SIZE      (int)1e3
 
int vertex_num[MAX_VERTICES];
bool visited_flag[MAX_VERTICES];
int from[MAX_VERTICES];
 
typedef struct {
 
	int u, v;
    int cap, flow;
    int next;
 
} edge;
 
edge edges[MAX_EDGES];
 
int T, K, N, V, E;
int src, snk;   /* Source & sink indices */
 
void add_edge(int u, int v, int cap);
bool augment(int src, int snk);
void dfs(int u, int snk);
 
int main() {
 
    int i;
    int nxt_intersection;
    char space;
    int paths = 0;
 
    /* Process each test case */
	while (++T) {
 
		scanf("%d %d", &K, &N);
 
        /* End of case: 0 0 sequence */
		if (!K && !N) break;
 
		src = 2 * 0 + 1;
		snk = 2 * 1;
		V = 2 * N;
		E = 0;
 
        for (i = 0; i <= V; i++) vertex_num[i] = -1;
 
        /* Scan intersections */
		for (i = 0; i < N; i++) {
 
			while (true) {
 
                /* Get a single adjacent intersection */
				scanf("%d%c", &nxt_intersection, &space);
                /* Decrement intersection idx since they start from 1 */
				nxt_intersection--;
 
                /* Init an edge */
				add_edge(2 * i + 1, 2 * nxt_intersection, INF);
 
                /* Adjacent intersections ended */
				if (space == '\n') break;
 
			}
 
            /* Init an edge */
		    add_edge(2 * i, 2 * i + 1, 1);
 
		}
 
        /* Calc paths */
        paths = 0;
		while (paths < K && augment(src, snk)) {
 
            paths++;
 
        }
 
		printf("Case %d:\n", T);
 
		if (paths < K) {
 
			printf("Impossible\n");
 
        /* There are K non-intersecting routes from the start (1) to the end (2) */
		} else {
 
			for (i = 0; i < K; i++) {
 
				dfs(src, snk);
				printf("2\n");
 
			}
 
		}
 
		printf("\n");
 
	}
 
	return 0;
 
}
 
 
void add_edge(int u, int v, int cap) {
 
    /* Set direct edge */
	edges[E] = (edge){u, v, cap, 0, vertex_num[u]};
	vertex_num[u] = E++;
 
    /* Set inverse edge */
	edges[E] = (edge){v, u, cap, cap, vertex_num[v]};
	vertex_num[v] = E++;
 
}
 
 
/* Augment graph */
bool augment(int src, int snk) {
 
    int i;
    int u, v;
    int queue[QUEUE_SIZE];  /* Won't shift all items when dequeue happens */
    int queue_front = 0, queue_back = 0;
 
    for (i = 0; i <= V; i++) visited_flag[i] = false;
	visited_flag[src] = true;
 
    /* Loop untill sink is visited or queue is empty */
    queue[queue_back++] = src;
    while ((queue_back - queue_front > 0) && (!visited_flag[snk])) {
 
        u = queue[queue_front];
 
        /* Loop through vertex sequence */
		for (i = vertex_num[u]; i != -1; i = edges[i].next) {
 
            v = edges[i].v;
 
			if ((!visited_flag[v]) && (edges[i].flow < edges[i].cap)) {
 
				visited_flag[v] = true;
				from[v] = i;
                assert(queue_back < QUEUE_SIZE);
                queue[queue_back++] = v;
 
			}
 
		}
 
        queue_front++;
 
    }
 
	if (!visited_flag[snk]) return false;
 
	for (i = snk; i != src; i = edges[from[i]].u) {
 
		edges[from[i]].flow++;
		edges[from[i] ^ 1].flow--;
 
	}
 
	return true;
 
}
 
 
/* Depth First Search algo */
void dfs(int u, int snk) {
 
    int i;
    int v;
 
	if (u == snk) return;
 
	if (u % 2) printf("%d ", (u / 2) + 1);
 
	for (i = vertex_num[u]; i != -1; i = edges[i].next) {
 
        v = edges[i].v;
		if ((edges[i].flow > 0) && (i % 2 == 0)) {
 
			edges[i].flow--;
			dfs(v, snk);
			break;
 
		}
 
	}
 
}