Path
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2452 Accepted Submission(s): 677
Problem Description
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl's home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can't reach his girl's house in the very beginning, the answer is obviously zero. And you don't need to guarantee that there still exists a way from Jerry's house to his girl's after blocking some edges.
Input
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤109), denoting that there exists a one-way road from the house indexed x to y of length c.
Output
Print T lines, each line containing a integer, the answer.
Sample Input
1 3 4 1 2 1 2 3 1 1 3 2 1 3 3
Sample Output
3
Source
2019 Multi-University Training Contest 1
这题裸中裸
太久没手撕最短路和网络流了
写了好久
#include<bits/stdc++.h>
using namespace std;
long long first[10005];
long long nxt[20005];
long long from[20005];
long long to[20005];
long long wi[20005];
long long vis[10005];
long long havev[20005];
long long cnt=0;
long long ccnt=-1;
long long ffirst[10005];
long long fnxt[20005];
long long fto[20005];
long long cfirst[10005];//网络流数组
long long cnxt[20005];
long long cto[20005];
long long cf[20005];
long long cc[20005];
long long n,m;
void add(long long u,long long v,long long w)// 加一个正边一个反边
{
cnt++;
from[cnt]=u;
nxt[cnt]=first[u];
first[u]=cnt;
to[cnt]=v;
wi[cnt]=w;
fnxt[cnt]=ffirst[v];
ffirst[v]=cnt;
fto[cnt]=u;
}
void cadd(long long u,long long v,long long w)
{
ccnt++;
cnxt[ccnt]=cfirst[u];
cfirst[u]=ccnt;
cc[ccnt]=w;
cf[ccnt]=0;
cto[ccnt]=v;
ccnt++;
cnxt[ccnt]=cfirst[v];
cfirst[v]=ccnt;
cc[ccnt]=0;
cf[ccnt]=0;
cto[ccnt]=u;
}
long long dis[10005];
void spfa(long long x)
{
queue<int> q;
q.push(1),vis[1]=1;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
while(q.size())
{
long long tmp=q.front();
q.pop(),vis[tmp]=0;
for(long long i=first[tmp];i!=-1;i=nxt[i])
{
long long v=to[i];
if(dis[tmp]+wi[i]<dis[v])
{
dis[v]=dis[tmp]+wi[i];
vis[v]=1;
q.push(v);
}
}
}
}
const long long INF = 0x7fffffff;
long long level[10005];
bool dinic_bfs() //bfs方法构造层次网络
{
//cout<<"level"<<endl;
queue<int> q;
memset(level, 0, sizeof(level));//每次全都重新分层
q.push(1);//把源点推入初始点
level[1] = 1;
long long u, v;
while (!q.empty())
{
u = q.front();
q.pop();
for (long long i=cfirst[u];i!=-1;i=cnxt[i])
{
v=cto[i];
if (!level[v] && cc[i]>cf[i])
{
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[n] != 0; //question: so it must let the sink node is the Mth?/the way of yj is give the sink node's id
}
long long dinic_dfs(long long u, long long cp) //use dfs to augment the flow
{
long long tmp = cp;
long long v, t;
if (u == n)
return cp;
for (long long i=cfirst[u];i!=-1&&tmp;i=cnxt[i])
{
v=cto[i];
if (level[u] + 1 == level[v])
{
if (cc[i]>cf[i])
{
// cout<<u<<" "<<v<<cc[i]<<" "<<
t = dinic_dfs(v, min(tmp, cc[i]-cf[i]));
cf[i] += t;
cf[i^1] -= t;
tmp -= t;
}
}
}
return cp - tmp;
}
long long dinic()
{
long long sum=0, tf=0;
while (dinic_bfs())
{
while (tf = dinic_dfs(1, INF))
sum += tf;
}
return sum;
}
int main()
{
//freopen("in.txt","r",stdin);
long long t;
scanf("%lld",&t);
while(t--)
{
cnt=0;
ccnt=-1;
memset(havev,0,sizeof(havev));
memset(first,-1,sizeof(first));
memset(cfirst,-1,sizeof(cfirst));
memset(ffirst,-1,sizeof(ffirst));
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=m;i++)
{
long long tmp1,tmp2,tmp3;
scanf("%lld%lld%lld",&tmp1,&tmp2,&tmp3);
add(tmp1,tmp2,tmp3);
}
spfa(1);
//cout<<"disn"<<dis[n]<<endl;
for(long long i=1;i<=cnt;i++)
{
for(long long j=first[i];j!=-1;j=nxt[j])
{
if(dis[from[j]]==dis[to[j]]-wi[j])
cadd(from[j],to[j],wi[j]);
//cout<<from[i]<<" "<<to[i]<<" "<<wi[i]<<endl;
}
}
long long ans=dinic();
printf("%lld
",ans);
}
return 0;
}