POJ 1637 Sightseeing tour 혼합 투 올 라 회 로 최대 흐름
사고방식: 문제 가 되 었 으 니 바로 문 제 를 보고 풀 어 라.
http://www.cnblogs.com/Lyush/archive/2013/05/01/3052847.html
CODE:
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 510
#define MAXE 5000000
#define INF 0x3f3f3f3f
#define S 0
#define T (MAX - 1)
using namespace std;
#define min(a,b) ((a) < (b) ? (a):(b))
#define max(a,b) ((a) > (b) ? (a):(b))
struct Edge{
int x,y;
bool directed;
void Read() {
int z;
scanf("%d%d%d",&x,&y,&z);
directed = z;
}
}edge[MAXE];
struct MaxFlow{
int head[MAX],total;
int next[MAXE],aim[MAXE],flow[MAXE];
int deep[MAX];
void Initialize() {
total = 1;
memset(head,0,sizeof(head));
}
void Add(int x,int y,int f) {
next[++total] = head[x];
aim[total] = y;
flow[total] = f;
head[x] = total;
}
void Insert(int x,int y,int f) {
Add(x,y,f);
Add(y,x,0);
}
bool BFS() {
static queue<int> q;
while(!q.empty()) q.pop();
memset(deep,0,sizeof(deep));
deep[S] = 1;
q.push(S);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = next[i])
if(flow[i] && !deep[aim[i]]) {
deep[aim[i]] = deep[x] + 1;
q.push(aim[i]);
if(aim[i] == T) return true;
}
}
return false;
}
int Dinic(int x,int f) {
if(x == T) return f;
int temp = f;
for(int i = head[x]; i; i = next[i])
if(deep[aim[i]] == deep[x] + 1 && flow[i] && temp) {
int away = Dinic(aim[i],min(flow[i],temp));
flow[i] -= away;
flow[i^1] += away;
temp -= away;
}
return f - temp;
}
}solver;
int _T;
int points,edges;
int in[MAX],out[MAX];
int sum;
inline bool Euler()
{
sum = 0;
for(int i = 1; i <= points; ++i) {
int degree = out[i] - in[i];
if(degree&1) return false;
degree >>= 1;
if(degree > 0) solver.Insert(S,i,degree),sum += degree;
else solver.Insert(i,T,-degree);
}
return true;
}
int main()
{
for(cin >> _T; _T--;) {
solver.Initialize();
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
scanf("%d%d",&points,&edges);
for(int i = 1; i <= edges; ++i) {
edge[i].Read();
if(edge[i].x == edge[i].y) continue;
if(!edge[i].directed) solver.Insert(edge[i].x,edge[i].y,1);
++in[edge[i].y],++out[edge[i].x];
}
if(!Euler()) {
puts("impossible");
continue;
}
int max_flow = 0;
while(solver.BFS())
max_flow += solver.Dinic(S,INF);
if(max_flow == sum) puts("possible");
else puts("impossible");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.