글 읽기 - 11495번 시간을 어떻게줄일수있을까요

wjdtmdrbs88 7년 전 1

네트워크플로우를 시작한지 얼마 되지않아 뭔가 시간줄이는 것이 어려운것같아요

나름 줄여본다고 2차원벡터 초기화까지 써서 반복을 줄였지만 시간초과네요..

어떻게 줄여볼수있을까요

저는 각 좌표 즉 0,0이라는 곳을 0번정점, 0,1을 1번정점 ... 이렇게 놓고 정점을 연결하는 방법을 사용하였습니다.

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321

#define MAX_N 2500
#define MAX_V 2502
const int S = MAX_V-2;
const int E = MAX_V-1;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};

class point
{
	public:
		int val,num;
};

int n,m;
point arr[51][51];
int main()
{
	int t; cin >> t;
	while(t--)
	{
		int sum = 0;
		vector<int> adj[MAX_V];
		scanf("%d%d", &n, &m);
		vector< vector<int> > c(MAX_V, vector<int>(MAX_V, 0));
		vector< vector<int> > f(MAX_V, vector<int>(MAX_V, 0));

		int Number=0;
		for(int i  = 0 ; i < n ; i++)
			for(int j = 0 ; j < m ; j++)
			{
				// val 은 가지는 값이고(입력값) 각자 정점 번호를 줌  
				scanf("%d", &arr[i][j].val);
				sum += arr[i][j].val;
				arr[i][j].num = Number++;
			}
		for(int i = 0 ; i < n ; i++)
		{
			int flag;
			if( i % 2 == 0) flag = 0;
			else flag = 1;
			for(int j = 0 ; j < m; j++)
			{
				if(flag == 0)
				{
					for(int k = 0 ; k < 4 ; k++)
					{
						int ny = i + dy[k];
						int nx = j + dx[k];
						if(ny > n-1 || ny < 0 || nx > m-1 || nx < 0)
							continue;
						c[arr[i][j].num][arr[ny][nx].num] = 1;
						adj[arr[i][j].num].push_back(arr[ny][nx].num);
						adj[arr[ny][nx].num].push_back(arr[i][j].num);
					}
					
					//시작점에서 해당 점으로 가는길 
					c[S][arr[i][j].num] = arr[i][j].val;
					adj[S].push_back(arr[i][j].num);
					adj[arr[i][j].num].push_back(S);
					flag = 1;
				}
				
				else
				{
					c[arr[i][j].num][E] = arr[i][j].val;
					adj[arr[i][j].num].push_back(E);
					adj[E].push_back(arr[i][j].num);
					flag = 0;
				}
			}
		}
		
		int res = 0;
		
		while(1)
		{
			vector<int> p(MAX_V,INF);
			queue<int> q;
			q.push(S);
			
			while(!q.empty())
			{
				int here = q.front();
				q.pop();
				
				for(int i = 0 ; i < adj[here].size(); i++)
				{
					int there = adj[here][i];
					if( c[here][there] - f[here][there] > 0 && p[there] == INF)
					{
						p[there] = here;
						q.push(there);
						if(there == E) break;
					}
				}
			}
			
			if(p[E] == INF)
				break;
			int flow = INF;
			for(int i = E ; i != S ; i = p[i])
				flow = min(flow, c[p[i]][i] - f[p[i]][i]);
			for(int i = E ; i != S ; i = p[i])
			{
				f[p[i]][i] += flow;
				f[i][p[i]] -= flow;
			}
			res += flow;
		}
		printf("%d\n", sum-res);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11495번 시간을 어떻게줄일수있을까요

wjdtmdrbs88 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말