Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个c++代码

Posted by a280920481 at 2019-02-26 23:26:16 on Problem 2112
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;


const int INF = 1 << 24;
const int MAX_N = 235;
const int MAX_V = 655;


struct Edge
{
	int to;
	int cap;
	int rev;
}G[MAX_V][MAX_V];
int deg[MAX_V];

int level[MAX_V];
int iter[MAX_V];

void add_edge(int from, int to, int cap);
void bfs(const int & s);
int que[MAX_V];
int dfs(const int & v, const int & t, int f);
int max_flow(int s, int t);


int MAT[MAX_N][MAX_N];
void warshall_floyd(int n);

int dist[MAX_N * MAX_V];

int _min(int & a, int b);


int main()
{
	int K, C, M, N, x;

	scanf("%d%d%d", &K, &C, &M);

	N = K + C;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &x);
			MAT[i][j] = x ? x : INF;
		}
	}

	warshall_floyd(N);

	int ds = 0;
	for (int i = 0; i < K; i++)
	{
		for (int j = K; j < N; j++)
		{
			dist[ds++] = MAT[i][j];
		}
	}
	sort(dist, dist + ds);

	int d = 0;
	for (int i = 1; i < ds; i++)
	{
		if (dist[i] == dist[i - 1])
		{
			d++;
		}
		else
		{
			dist[i - d] = dist[i];
		}
	}
	ds -= d;

	int S = N;
	int T = S + 1;

	int lb = -1, rb = ds - 1, mid;
	while (rb - lb > 1)
	{
		mid = (lb + rb) >> 1;

		memset(deg, 0, sizeof(deg));
		for (int i = 0; i < K; i++)
		{
			add_edge(S, i, M);
			for (int j = K; j < N; j++)
			{
				if (MAT[i][j] <= dist[mid])
				{
					add_edge(i, j, 1);
				}
			}
		}
		for (int i = K; i < N; i++)
		{
			add_edge(i, T, 1);
		}

		if (max_flow(S, T) == C)
		{
			rb = mid;
		}
		else
		{
			lb = mid;
		}
	}

	printf("%d\n", dist[rb]);
	
	return 0;
}


void add_edge(int from, int to, int cap)
{
	Edge e1 = { to,cap,deg[to] };
	Edge e2 = { from, 0, deg[from] };
	G[from][deg[from]++] = e1;
	G[to][deg[to]++] = e2;
}

void bfs(const int & s)
{
	int lb = 0, rb = 0;
	memset(level, -1, sizeof(level));
	level[s] = 0;
	que[rb++] = s;

	while (lb != rb)
	{
		int v = que[lb++];
		for (int i = 0; i < deg[v]; i++)
		{
			Edge & e = G[v][i];
			if (e.cap && level[e.to] == -1)
			{
				level[e.to] = level[v] + 1;
				que[rb++] = e.to;
			}
		}
	}
}

int dfs(const int & v, const int & t, int f)
{
	static int d;

	if (v == t)
	{
		return f;
	}

	for (int & i = iter[v]; i < deg[v]; i++)
	{
		Edge & e = G[v][i];
		if (e.cap && level[v] < level[e.to])
		{
			d = dfs(e.to, t, f < e.cap ? f : e.cap);
			if (d)
			{
				e.cap -= d;
				G[e.to][e.rev].cap = d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s, int t)
{
	int flow = 0;
	int f;

	do
	{
		bfs(s);
		memset(iter, 0, sizeof(iter));
		while (f = dfs(s, t, INF))
		{
			flow += f;
		}
	} while (level[t] >= 0);
	return flow;
}

void warshall_floyd(int n)
{
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				MAT[i][j] = _min(MAT[i][j], MAT[i][k] + MAT[k][j]);
			}
		}
	}
}

int _min(int & a, int b)
{
	return a < b ? a : b;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator