Admiral Time Limit: 3000MS 64bit IO Format: %lld & %llu
Description
对于这道题，每个节点只能走一次，那么就可以拆成两个点，中间连一条cap为1的边，然后最小费用流搞定。
#include<iostream> #include<cstdio> #include<cstring> #include<deque> #include<queue> #include<vector> using namespace std; const int maxe=10005; const int maxv=1005<<2; const int INF=0x3f3f3f3f; struct Edge { int to,next; int cap,cost; }edge[(maxe+maxv)<<1]; int head[maxv<<1]; int maxedge; inline void addedge(int u,int v,int cap,int cost) { edge[++maxedge]=(Edge){v,head[u],cap,cost}; head[u]=maxedge; edge[++maxedge]=(Edge){u,head[v],0,-cost}; head[v]=maxedge; } int n,m,S,T; inline bool init() { maxedge=-1; memset(head,-1,sizeof(head)); if(!~scanf("%d%d",&n,&m)) return false; S=(n<<1)+1,T=(n<<1)+2; addedge(S,1,2,0);addedge(n<<1,T,2,0); int u,v,cost; for(int i=1;i<=n;i++) if(i!=1&&i!=n) addedge(i,i+n,1,0); else addedge(i,i+n,2,0); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&cost); addedge(u+n,v,1,cost); } return true; } int dis[maxv<<1],inque[maxv<<1],add[maxv<<1],pre[maxv<<1]; inline bool spfa() { deque <int> que; memset(dis,0x3f,sizeof(dis)); memset(pre,-1,sizeof(pre)); inque[S]=true;add[S]=INF;dis[S]=0; que.push_back(S); while(!que.empty()) { int u=que.front();que.pop_front();inque[u]=false; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap==0) continue; if(dis[v]>dis[u]+edge[i].cost) { dis[v]=dis[u]+edge[i].cost; add[v]=min(add[u],edge[i].cap); pre[v]=i; if(inque[v]) continue; inque[v]=true; if(!que.empty()) if(dis[v]<dis[que.front()]) que.push_front(v); else que.push_back(v); else que.push_back(v); } } } if(dis[T]==INF) return false; return true; } inline int MCMF() { int flow=0,cost=0; while(spfa()) { flow+=add[T];cost+=dis[T]*add[T];//a muiltiply! for(int i=pre[T];~i;i=pre[edge[i^1].to]) { edge[i].cap-=add[T]; edge[i^1].cap+=add[T]; } } // if(flow!=2) cout<<"Error"<<endl; return cost; } int main() { #ifdef Local freopen("admiral.in","r",stdin); freopen("admiral.out","w",stdout); #endif while(init()) printf("%d\n",MCMF());//multiple judgements!! return 0; }