zoj 3885 Exchange of Items[최소 비용 최대 흐름]
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Bob lives in an ancient village, where transactions are done by one item exchange with another. Bob is very clever and he knows what items will become more valuable later on. So, Bob has decided to do some business with villagers.
At first, Bob has N kinds of items indexed from 1 to N, and each item has Ai. There are M ways to exchanges items. For the ith way (Xi, Yi), Bob can exchange one Xith item to oneYith item, vice versa. Now Bob wants that his ith item has exactly Bi, and he wonders what the minimal times of transactions is.
Input
There are multiple test cases. For each test case: the first line contains two integers: N and M (1 <= N, M <= 100). The next N lines contains two integers: Ai and Bi (1 <= Ai, Bi <= 10,000). Following M lines contains two integers: Xi and Yi (1 <= Xi, Yi <= N). There is one empty line between test cases.
Output
For each test case output the minimal times of transactions. If Bob could not reach his goal, output -1 instead.
Sample Input
2 1
1 2
2 1
1 2
4 2
1 3
2 1
3 2
2 3
1 2
3 4
Sample Output
1
-1
Author:
FENG, Jingyi
Source: ZOJ Monthly, July 2017
제목: Bob은 N가지 물품이 있습니다. 모든 물품에 Ai개가 있는 것으로 알고 있습니다. 지금 그는 Bi개로 바꾸고 싶습니다.M가지 교환 방식
사고방식: 최소 비용의 최대 흐름.목표 상태의 총 유량sum를 기록하고 환점에 유입된 총 유량이sum인지 판단한다.목표 상태가 도달할 수 있음을 설명하는 것과 같으면 최소 비용을 출력하고, 반대로 도달할 수 없으면 출력-1을 출력한다.
건도: 슈퍼 소스 소스, 슈퍼 송금sink를 설정합니다.
1,source는 모든 물품에 변경을 하고 용량은 물품의 초기 수량이며 비용은 0이다.
2, 모든 물품은sink에 변경을 건설하고 용량은 물품의 목표 수량이며 비용은 0이다.
3. M종 변환 관계는 양방향 모서리를 만들고 용량은 INF(목표 상태에 도달하기 위해 우리는 임의로 이 모서리의 유량을 선택할 수 있음)이며 비용은 1이다.
최소 비용의 최대 흐름을 다시 한 번 뛰고 마지막 최대 흐름flow가 목표 상태의 총 유량과 같으면 최소 비용cost를 출력하고 반대로 출력-1을 출력한다.
AC 코드:
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define MAXN 110
#define MAXM 1000
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int from, to, cap, flow, cost, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum;
int pre[MAXN], dist[MAXN];
bool vis[MAXN];
int source, sink;//
int N, M;
int sum;//
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w, int c)
{
Edge E1 = {u, v, w, 0, c, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
Edge E2 = {v, u, 0, 0, -c, head[v]};
edge[edgenum] = E2;
head[v] = edgenum++;
}
void getMap()
{
int a, b;
sum = 0;
source = 0, sink = N+1;
for(int i = 1; i <= N; i++)
{
scanf("%d%d", &a, &b);
addEdge(source, i, a, 0);// i a 0
addEdge(i, sink, b, 0);//i b 0
sum += b;//
}
for(int i = 1; i <= M; i++)
scanf("%d%d", &a, &b),
addEdge(a, b, INF, 1), addEdge(b, a, INF, 1);// 1
}
bool SPFA(int s, int t)
{
queue<int> Q;
memset(dist, INF, sizeof(dist));
memset(vis, false, sizeof(vis));
memset(pre, -1, sizeof(pre));
dist[s] = 0;
vis[s] = true;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow)
{
dist[E.to] = dist[u] + E.cost;
pre[E.to] = i;
if(!vis[E.to])
{
vis[E.to] = true;
Q.push(E.to);
}
}
}
}
return pre[t] != -1;
}
void MCMF(int s, int t, int &cost, int &flow)
{
cost = flow = 0;
while(SPFA(s, t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
Edge E = edge[i];
Min = min(Min, E.cap - E.flow);
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
init();
getMap();
int cost, flow;
MCMF(source, sink, cost, flow);
if(flow == sum)//
printf("%d
", cost);
else
printf("-1
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
