[tyvj-2054][Nescafé29]四叶草魔杖 费用流
2024-10-01 03:55:23
lyd讲的最小生成树的题。
道理我都懂,费用流多好写,又好调。但和一般费用流不一样的就是它走过一次后费用需调成0,但是再等回流,就恢复原状即可。
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int N=5050,S=0,T=5005,inf=0x3f3f3f3f;
int n,m,a[N],sum,ecnt=1,head[N],dis[N],from[N];
bool inq[N];
struct Edge {
int to,nxt,val,cost,from;
} e[1000010],fb[1000010];
void add(int bg,int ed,int val,int cost) {
e[++ecnt].cost=cost;e[ecnt].from=bg;e[ecnt].nxt=head[bg];e[ecnt].to=ed;
e[ecnt].val=val;head[bg]=ecnt;fb[ecnt]=e[ecnt];
}
void insert(int bg,int ed,int val,int cost) {
add(bg,ed,val,cost);
add(ed,bg,0,cost);
}
queue<int>q;
bool spfa() {
q.push(S);
std::memset(dis,0x3f,sizeof dis);
std::memset(inq,0,sizeof inq);
dis[S]=0;
inq[S]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u],v; i; i=e[i].nxt) {
v=e[i].to;
if(dis[v]>dis[u]+e[i].cost&&e[i].val) {
dis[v]=dis[u]+e[i].cost;
from[v]=i;
if(!inq[v]) q.push(v),inq[v]=1;
}
}
}
return dis[T]!=inf;
}
void min(int &x,int y) {x=x<y?x:y;}
int mincost,maxflow;
void mcf() {
int x=inf,i=from[T];
while(i) {min(x,e[i].val);i=from[e[i].from];}
i=from[T];maxflow+=x;
while(i) {
e[i].val-=x;
e[i^1].val+=x;
mincost+=x*e[i].cost;
if(e[i].val!=inf) {e[i].cost=0;e[i^1].cost=0;}
else{e[i].cost=fb[i].cost;e[i^1].cost=fb[i^1].cost;}
i=from[e[i].from];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++) {
scanf("%d",&a[i]);
if(a[i]>0)insert(S,i,a[i],0),sum+=a[i];
else if(a[i]<0)insert(i,T,-a[i],0);
}
for(int i=1,s,t,x;i<=m;i++) scanf("%d%d%d",&s,&t,&x),add(++s,++t,inf,x),add(t,s,inf,x);//注意
while(spfa()) mcf();
if(maxflow==sum){
mincost=0;
for(int i=2;i<=ecnt;i++) {if(e[i].val&&e[i].val!=inf) mincost+=fb[i].cost;}
cout<<mincost/2;
return 0;
}
puts("Impossible");
}
最新文章
- Python的魔法函数之 - __len__,__getitem__,__setitem__,__delitem__
- 【转】一个URL编码和解码的C++类
- readonly和const区别
- 转载:Python中的new style class机制实现
- Android GreenDao with Android Studio IDE
- 有关spring-servlet.xml 和 application.xml的配置信息讲解(这两个配置信息的区别在哪里)
- myBatis系列之七:事务管理
- addslashes() 函数返回在预定义字符之前添加反斜杠的字符串
- 201421123042 《Java程序设计》第6周学习总结
- centos7之zabbix的web检测
- [Swift]LeetCode911. 在线选举 | Online Election
- Lintcode487-Name Deduplication-Easy
- 【HAOI2010】软件安装
- [Java.Web] Servlet 的一些细节
- thinkphp5实现定位功能
- Notes of the scrum meeting(12.10)
- 你可能从未听过的 Linux 发行版
- POJ 3613 Cow Relays (floyd + 矩阵高速幂)
- 机器学习基础之knn的简单例子
- js执行环境、作用域
热门文章
- [bzoj2259][Oibh]新型计算机_Dijkstra
- NEFU116 GCD
- winrar为啥有广告了?能去掉么?
- ps -ef与ps aux的区别
- springmvc 监听器getWriter() has already been called for this response问题
- pl/sql developer 自动输入替换 光标自动定位
- C语言高速入门系列(一)
- ios swift学习日记4-字符串和字符
- TextView高级
- python spark 求解最大 最小 平均 中位数