補題：跑兩個最短路取出最短邊跑最小割，全是模版，最短路初值附小了，找了好久的bug

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
#define pii make_pair
#define pr pair<ll,ll>
typedef long long ll;
const int inff=0x3f3f3f3f;
const long long inFF=9223372036854775807;
const int dir[4][2]={0,1,0,-1,1,0,-1,0};
const double eps=1e-10;
const double E=2.718281828459;
const double pi=acos(-1.0);
typedef unsigned long long ull;
using namespace std;
const int maxn=1e4+100;
struct p
{ll first,second;bool friend operator<(p s,p e){return s.first>s.first;}
};
struct nod
{ll x,y,val;
}a[maxn];
struct node
{ll to,p;ll val;
}edge[maxn<<1],qedge[maxn<<1],qqedge[maxn<<1];
ll n,m;
ll d[maxn],d1[maxn],d2[maxn];
ll head[maxn],qhead[maxn],qqhead[maxn],qqsign,sign,qsign;
ll cur[maxn];
void add(ll u,ll v,ll val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;qedge[qsign]=node{u,qhead[v],val};qhead[v]=qsign++;
}
void qqadd(ll u,ll v,ll val)
{qqedge[qqsign]=node{v,qqhead[u],val};qqhead[u]=qqsign++;qqedge[qqsign]=node{u,qqhead[v],0};qqhead[v]=qqsign++;
}
void init()
{sign=qsign=qqsign=0;for(ll i=0;i<=n+1;i++) head[i]=qhead[i]=qqhead[i]=-1;
}
ll dij1()
{for(ll i=1;i<=n;i++) d1[i]=inFF;d1[1]=0;priority_queue<p> q;q.push(p{0,1});while(!q.empty()){p now=q.top();q.pop();if(d1[now.second]<now.first) continue;for(ll i=head[now.second];~i;i=edge[i].p){ll v=edge[i].to;if(d1[v]>d1[now.second]+edge[i].val){d1[v]=edge[i].val+d1[now.second];q.push(p{d1[v],v});}}}return d1[n];
}
void dij2()
{for(ll i=0;i<=n;i++) d2[i]=inFF;d2[n]=0;priority_queue<p> q;q.push(p{0,n});while(!q.empty()){p now=q.top();q.pop();if(d2[now.second]<now.first) continue;for(ll i=qhead[now.second];~i;i=qedge[i].p){ll v=qedge[i].to;if(d2[v]>d2[now.second]+qedge[i].val){d2[v]=qedge[i].val+d2[now.second];q.push(p{d2[v],v});}}}
}
ll dfs(ll u,ll ed,ll low)
{if(u==ed) return low;ll temp=low,a;for(ll &i=cur[u];~i;i=qqedge[i].p){ll v=qqedge[i].to;if(d[v]==d[u]+1&&qqedge[i].val){if(a=dfs(v,ed,min(low,qqedge[i].val))){qqedge[i].val-=a;qqedge[i^1].val+=a;temp-=a;if(temp==0) break;}}}return low-temp;
}
bool bfs(ll st,ll ed)
{memset(d,0,sizeof(d));d[st]=1;queue<ll> q;q.push(st);while(!q.empty()){ll u=q.front();q.pop();for(ll i=qqhead[u];~i;i=qqedge[i].p){ll v=qqedge[i].to;if(!d[v]&&qqedge[i].val){d[v]=d[u]+1;q.push(v);}}}if(d[ed]>0) return true;return false;
}
ll dinic()
{ll ans=0;while(bfs(0,n)){for(ll i=0;i<=n;i++)cur[i]=qqhead[i];ans+=dfs(0,n,inff);}return ans;
}
int main()
{ll t;freopen("g://2.in","r",stdin);freopen("g://3.out","w",stdout);cin>>t;while(t--){cin>>n>>m;init();for(ll i=1;i<=m;i++){scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].val);add(a[i].x,a[i].y,a[i].val);}ll ans=dij1();dij2();n++;for(ll i=1;i<=m;i++){if(d1[a[i].x]+d2[a[i].y]+a[i].val==ans)qqadd(a[i].x,a[i].y,a[i].val);}qqadd(0,1,inff),qqadd(n-1,n,inff);ans=dinic();cout<<ans<<endl;}return 0;
}

?

總結

以上是生活随笔為你收集整理的Path HDU6582的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。