HDU 1853
9769 단어 HDU
다음 문제 와 똑 같 습 니 다. 그림 의 고 리 를 구하 고 이 문제 의 문 제 는 매우 드 러 났 습 니 다.
http://www.cnblogs.com/xiaohongmao/p/3873957.html
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std ;
const int INF=0xfffffff ;
struct node{
int s,t,cap,cost,nxt ;
}e[200005] ;
int sumflow ;
int n,m,cnt,head[10005],vis[10005],dis[10005],pre[10005] ;
void add(int s,int t,int cap,int cost)
{
e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].cost=cost ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;
e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].cost=-cost ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;
}
int spfa(int s,int t,int N)
{
for(int i=0 ;i<=N ;i++)
dis[i]=INF ;
dis[s]=0 ;
memset(vis,0,sizeof(vis)) ;
memset(pre,-1,sizeof(pre)) ;
vis[s]=1 ;
queue <int> q ;
q.push(s) ;
while(!q.empty())
{
int u=q.front() ;
q.pop() ;
vis[u]=0 ;
for(int i=head[u] ;i!=-1 ;i=e[i].nxt)
{
int tt=e[i].t ;
if(e[i].cap && dis[tt]>dis[u]+e[i].cost)
{
dis[tt]=dis[u]+e[i].cost ;
pre[tt]=i ;
if(!vis[tt])
{
vis[tt]=1 ;
q.push(tt) ;
}
}
}
}
if(dis[t]==INF)return 0 ;
return 1 ;
}
int MCMF(int s,int t,int N)
{
int flow,minflow,mincost ;
mincost=flow=0 ;
while(spfa(s,t,N))
{
minflow=INF ;
for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s])
minflow=min(minflow,e[i].cap) ;
flow+=minflow ;
for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s])
{
e[i].cap-=minflow ;
e[i^1].cap+=minflow ;
}
mincost+=dis[t]*minflow ;
}
sumflow=flow ;//
return mincost ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
cnt=0 ;
memset(head,-1,sizeof(head)) ;
int S=0 ;
int T=2*n+1 ;
for(int i=0 ;i<m ;i++)
{
int s,t,v ;
scanf("%d%d%d",&s,&t,&v) ;
add(s,t+n,1,v) ;
}
for(int i=1 ;i<=n ;i++)
add(S,i,1,0) ;
for(int i=n+1 ;i<=2*n ;i++)
add(i,T,1,0) ;
int ans=MCMF(S,T,T+1) ;
if(sumflow!=n)puts("-1") ;
else printf("%d
",ans) ;
}
return 0 ;
}
View Code
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.