开了long long 过了5个点
by walk_alone @ 2020-08-12 10:38:55
调了一下午依旧50分……
```cpp
#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
const long long maxn=0x3f3f3f3f3f3f3f3f;
struct line
{
long long from;
long long to;
long long dis;
long long v;
long long next;
long long sign;
};
struct line que[800005];
struct node
{
long long id;
long long dis;
bool operator<(const node &b)const
{
return dis>b.dis;
}
};
int n,headers[40005],depth[400005],sign[40005],book[40005],cnt;
long long dis[40005];
void add(long long from,long long to,long long v,long long cost)
{
que[cnt].from=from;
que[cnt].to=to;
que[cnt].v=v;
que[cnt].dis=cost;
que[cnt].next=headers[from];
headers[from]=cnt;
cnt++;
}
void spfa(int s)
{
memset(dis,maxn,sizeof(dis));
dis[s]=0;
queue<int>q;
q.push(s);
book[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
book[x]=0;
for(int i=headers[x];i!=-1;i=que[i].next)
if(dis[x]+que[i].dis<dis[que[i].to])
{
dis[que[i].to]=dis[x]+que[i].dis;
if(!book[que[i].to])
{
book[que[i].to]=1;
q.push(que[i].to);
}
}
}
}
bool bfs(int s,int t)
{
memset(depth,0,sizeof(depth));
queue<int>q;
q.push(s);
depth[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=headers[u];i!=-1;i=que[i].next)
if(!depth[que[i].to] && que[i].v>0 && que[i].sign)
{
depth[que[i].to]=depth[u]+1;
q.push(que[i].to);
}
}
return depth[t];
}
long long dfs(int u,int t,long long flow)
{
if(u==t || flow<=0)
return flow>0?flow:0;
for(int i=headers[u];i!=-1;i=que[i].next)
if(depth[que[i].to]==depth[u]+1 && que[i].sign)
{
long long d=dfs(que[i].to,t,min(flow,que[i].v));
if(d>0)
{
que[i].v-=d;
que[i^1].v+=d;
return d;
}
}
depth[u]=-1;
return 0;
}
long long dinic(int s,int t)
{
long long ans=0;
while(bfs(s,t))
{
long long x=1;
while(x)
{
x=dfs(s,t,maxn);
ans+=x;
}
}
return ans;
}
int main()
{
int m,a,b;
long long c;
scanf("%d%d",&n,&m);
memset(headers,-1,sizeof(headers));
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&a,&b,&c);
add(a*2,b*2-1,maxn,c);
add(b*2-1,a*2,0,c);
add(b*2-1,a*2,maxn,c);
add(a*2,b*2-1,0,c);
}
add(1,2,maxn,0);
add(2,1,0,0);
add(2*n-1,2*n,maxn,0);
add(2*n,2*n-1,0,0);
for(int i=1;i<=n;i++)
{
scanf("%lld",&c);
if(i!=1 && i!=n)
{
add(2*i-1,2*i,c,0);
add(2*i,2*i-1,0,0);
}
}
spfa(1);
for(int i=0;i<cnt;i++)
if(dis[que[i].to]==dis[que[i].from]+que[i].dis)
que[i].sign=que[i^1].sign=1;
printf("%lld",dinic(1,n*2));
return 0;
}
```
如果不想看代码，蒟蒻能要组小数据吗（卑微）
by walk_alone @ 2020-08-12 17:01:14