원제:http://poj.org/problem?id=1087
제목: n 개의 콘센트, m 개의 전기 와 그 에 대응 하 는 콘센트, k 종의 변환기, 변환기 (u, v) 는 u 콘센트 가 필요 한 전 기 를 v 콘센트 에 연결 할 수 있 음 을 나타 낸다. 최소 몇 개의 장치 가 콘센트 가 없 는 지 물 어보 고 각 변환기 의 수량 은 제한 되 지 않 는 다.
#include
#include
#include
#include
#include
#include
#include
#define inf 1e9
using namespace std;
const int maxn = 1500;
const int maxm = 5500;
int n, m, k;
int num_nodes;
int a[30];
mapmp;
struct Edge
{
int from, to, flow, cap;
}edge[maxm*2];
vectorG[maxn];
int edgenum;
void add(int u, int v, int c)
{
edge[edgenum].from = u;
edge[edgenum].to = v;
edge[edgenum].flow = 0;
edge[edgenum].cap = c;
edgenum++;
edge[edgenum].from = v;
edge[edgenum].to = u;
edge[edgenum].flow = 0;
edge[edgenum].cap = 0;
edgenum++;
G[u].push_back(edgenum-2);
G[v].push_back(edgenum-1);
}
int deep[maxn];
bool vis[maxn];
void BFS(int s, int t)
{
queueQ;
memset(vis, false, sizeof vis);
Q.push(t);
vis[t] = true;
deep[t] = 0;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = 0;i e.flow && deep[begin] == deep[e.to] + 1)
{
front[e.to] = G[begin][i];
cur[begin] = i;
flag = true;
begin = e.to;
break;
}
}
if(!flag)
{
int k = num_nodes-1;
for(int i = 0;i e.flow)
k = min(k, deep[e.to]);
}
if(--gap[deep[begin]] == 0) break;
gap[deep[begin] = k+1]++;
cur[begin] = 0;
if(begin != s)
begin = edge[front[begin]].from;
}
}
return flow;
}
void init()
{
for(int i = 0;i
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[네트워크 흐름 24문제] [codevs1906] 최장 증자 서열 (dp+isap)
전송문 제목의 bug:1、데이터 범위는 주지 않았지만 눈대중으로 아무렇게나 열면 돼요.
한 점을 두 점으로 나누어 각 점의 사용 횟수를 보증하다.관계의 전이 dp 이후 i가 j 이전에 만족해야 하며 i의 값이 j의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
