[도 론]최소 비용 흐름 템 플 릿
/* ( )
* vector , G
* V ,
* :O(F*V^2)
*/
#define INF 0x3f3f3f3f
#define MAX_V 1005
typedef pair P;
struct edge
{
int to,cap,cost,rev;
};
int V;
vector G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge)
{
to,cap,cost,G[to].size()
});
G[to].push_back((edge)
{
from,0,-cost,G[from].size()-1
});
}
int min_cost_flow(int s,int t,int f)
{
int res=0;
fill(h,h+V,0);
while(f>0)
{
priority_queue ,greater
>que;
fill(dist,dist+V,INF);
dist[s]=0;
que.push(P(0,s));
while(!que.empty())
{
P p=que.top();
que.pop();
int v=p.second;
if(dist[v]
0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to])
{
dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t]==INF)
{
return -1;
}
for(int v=0; v
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
\# HDU 3790 최 단 경로 문제 [Dijkstra 입문 문제]n 개의 점 을 드 리 겠 습 니 다. m 개의 방향 이 없고 모든 변 에 길이 d 와 소비 p 가 있 습 니 다. 출발점 s 종점 t 를 드 리 겠 습 니 다. 출력 출발점 에서 종점 까지 의 최 단 거리 와 비용...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.