1 条题解
-
1
#include<bits/stdc++.h> #define il inline #define ll long long #define debug printf("%d %s\n",__LINE__,__FUNCTION__) using namespace std; const ll N=100005,inf=233333333333333,mod=2018; ll n,m,s,t,h[100],dis[2005],cnt=1; ll ans; struct edge{ ll to,net;ll v; }e[N]; il void add(ll u,ll v,ll w) { e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt; e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt; } queue<ll>q; il bool bfs() { memset(dis,-1,sizeof(dis)); q.push(s),dis[s]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].net) if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,q.push(e[i].to); } return dis[t]!=-1; } il ll dfs(ll u,ll op) { if(u==t)return op; ll flow=0,used=0; for(int i=h[u];i;i=e[i].net) { int v=e[i].to; if(dis[v]==dis[u]+1&&e[i].v>0) { used=dfs(v,min(op,e[i].v)); if(!used)continue; flow+=used,op-=used; e[i].v-=used,e[i^1].v+=used; if(!op)break; } } if(!flow)dis[u]=-1; return flow; } int main() { scanf("%lld%lld",&n,&m);s=1,t=n; ll u,v;ll w; for(int i=1;i<=m;i++) { scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w*mod+1); } while(bfs())ans+=dfs(s,inf); printf("%lld %lld\n",ans/mod,ans%mod); return 0; }
- 1
信息
- ID
- 345
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者