HDU - 6582 Path (最短路+最小割)

题意：给定一个n个点m条边的有向图，每条边有个长度，可以花费等同于其长度的代价将其破坏掉，求最小的花费使得从1到n的最短路变长。

解法：先用dijkstra求出以1为源点的最短路，并建立最短路图(只保留d[v]=d[u]+e[i].c的边(u,v))，跑个最大流即可。

Dinic:

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll N=1e4+,inf=0x3f3f3f3f3f3f3f3fll;

 ll n,m;

 struct MF {

     ll hd[N],ne,d[N],g[N],cur[N];

     struct E {ll v,cp,nxt;} e[N<<];

     void init() {memset(hd,-,sizeof hd),ne=;}

     void addedge(ll u,ll v,ll cp) {

         e[ne]= {v,cp,hd[u]},hd[u]=ne++;

         e[ne]= {u,,hd[v]},hd[v]=ne++;

     }

     int bfs(ll s,ll t) {

         queue<ll> q;

         memset(d,-,sizeof d);

         d[s]=,q.push(s);

         while(q.size()) {

             ll u=q.front();

             q.pop();

             for(ll i=hd[u]; ~i; i=e[i].nxt)if(e[i].cp) {

                     ll v=e[i].v;

                     if(!~d[v])d[v]=d[u]+,q.push(v);

                 }

         }

         return ~d[t];

     }

     ll dfs(ll t,ll u,ll f) {

         if(u==t||!f)return f;

         ll ret=;

         for(ll& i=cur[u]; ~i; i=e[i].nxt) {

             ll v=e[i].v;

             if(d[v]==d[u]+) {

                 ll df=dfs(t,v,min(f,e[i].cp));

                 e[i].cp-=df,e[i^].cp+=df,f-=df,ret+=df;

                 if(!f)return ret;

             }

         }

         return ret;

     }

     ll dinic(ll s,ll t) {

         ll ret=;

         while(bfs(s,t)) {

             for(ll i=; i<=n; ++i)cur[i]=hd[i];

             ret+=dfs(t,s,inf);

         }

         return ret;

     }

 } mf;

 struct SP {

     ll hd[N],ne,dp[N];

     struct E {ll v,c,nxt;} e[N];

     void init() {memset(hd,-,sizeof hd),ne=;}

     void addedge(ll u,ll v,ll c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;}

     struct D {

         ll u,g;

         bool operator<(const D& b)const {return b.g>g;}

     };

     priority_queue<D> q;

     void upd(ll u,ll ad) {if(dp[u]>ad)dp[u]=ad,q.push({u,ad});}

     void dij(ll s) {

         memset(dp,inf,sizeof dp);

         upd(s,);

         while(q.size()) {

             ll u=q.top().u,g=q.top().g;

             q.pop();

             if(dp[u]!=g)continue;

             for(ll i=hd[u]; ~i; i=e[i].nxt) {

                 ll v=e[i].v,c=e[i].c;

                 upd(v,g+c);

             }

         }

     }

     void solve() {

         dij();

         for(ll u=; u<=n; ++u) {

             for(ll i=hd[u]; ~i; i=e[i].nxt) {

                 ll v=e[i].v,c=e[i].c;

                 if(dp[v]==dp[u]+c)mf.addedge(u,v,c);

             }

         }

         printf("%lld\n",mf.dinic(,n));

     }

 } sp;

 int main() {

     ll T;

     for(scanf("%lld",&T); T--;) {

         sp.init(),mf.init();

         scanf("%lld%lld",&n,&m);

         while(m--) {

             ll u,v,c;

             scanf("%lld%lld%lld",&u,&v,&c);

             sp.addedge(u,v,c);

         }

         sp.solve();

     }

     return ;

 }

ISAP:

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll N=1e4+,inf=0x3f3f3f3f3f3f3f3fll;

 ll n,m;

 struct MF {

     ll hd[N],ne,d[N],g[N],cur[N];

     struct E {ll v,cp,nxt;} e[N<<];

     void init() {memset(hd,-,sizeof hd),ne=;}

     void addedge(ll u,ll v,ll cp) {

         e[ne]= {v,cp,hd[u]},hd[u]=ne++;

         e[ne]= {u,,hd[v]},hd[v]=ne++;

     }

     void bfs(ll s) {

         queue<ll> q;

         memset(d,-,sizeof d);

         memset(g,,sizeof g);

         ++g[d[s]=],q.push(s);

         while(q.size()) {

             ll u=q.front();

             q.pop();

             for(ll i=hd[u]; ~i; i=e[i].nxt) {

                 ll v=e[i].v;

                 if(!~d[v])++g[d[v]=d[u]+],q.push(v);

             }

         }

     }

     ll dfs(ll s,ll t,ll u,ll f) {

         if(u==t||!f)return f;

         ll ret=;

         for(ll& i=cur[u]; ~i; i=e[i].nxt) {

             ll v=e[i].v;

             if(d[v]==d[u]-) {

                 ll df=dfs(s,t,v,min(f,e[i].cp));

                 e[i].cp-=df,e[i^].cp+=df,f-=df,ret+=df;

                 if(!f)return ret;

             }

         }

         if(!--g[d[u]])d[s]=n+;

         ++g[++d[u]],cur[u]=hd[u];

         return ret;

     }

     ll isap(ll s,ll t) {

         ll ret=;

         bfs(t);

         for(ll i=; i<=n; ++i)cur[i]=hd[i];

         while(d[s]<n+)ret+=dfs(s,t,s,inf);

         return ret;

     }

 } mf;

 struct SP {

     ll hd[N],ne,dp[N];

     struct E {ll v,c,nxt;} e[N];

     void init() {memset(hd,-,sizeof hd),ne=;}

     void addedge(ll u,ll v,ll c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;}

     struct D {

         ll u,g;

         bool operator<(const D& b)const {return b.g>g;}

     };

     priority_queue<D> q;

     void upd(ll u,ll ad) {if(dp[u]>ad)dp[u]=ad,q.push({u,ad});}

     void dij(ll s) {

         memset(dp,inf,sizeof dp);

         upd(s,);

         while(q.size()) {

             ll u=q.top().u,g=q.top().g;

             q.pop();

             if(dp[u]!=g)continue;

             for(ll i=hd[u]; ~i; i=e[i].nxt) {

                 ll v=e[i].v,c=e[i].c;

                 upd(v,g+c);

             }

         }

     }

     void solve() {

         dij();

         for(ll u=; u<=n; ++u) {

             for(ll i=hd[u]; ~i; i=e[i].nxt) {

                 ll v=e[i].v,c=e[i].c;

                 if(dp[v]==dp[u]+c)mf.addedge(u,v,c);

             }

         }

         printf("%lld\n",mf.isap(,n));

     }

 } sp;

 int main() {

     ll T;

     for(scanf("%lld",&T); T--;) {

         sp.init(),mf.init();

         scanf("%lld%lld",&n,&m);

         while(m--) {

             ll u,v,c;

             scanf("%lld%lld%lld",&u,&v,&c);

             sp.addedge(u,v,c);

         }

         sp.solve();

     }

     return ;

 }

这道题Dinic居然比ISAP快，我的代码ISAP跑了156ms，而Dinic只跑了93ms..

巴特西

HDU - 6582 Path (最短路+最小割)

最新文章

热门文章