题解:

带下界的费用流

对于x->y边权为z Addedge(x,t,1,0) Addedge(s,y,1,z) Addedge(x,y,inf,0)

然后对每个点Addedge(i,1,inf,0)

然后跑最小费用最大流即可

因为这是DAG,所以每一个循环流都是从1到某个点再到1的路径

也就是说用几个费用最小的循环流来满足下界

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=3000;
const int oo=1000000000; int n;
struct Edge{
int from,to,cap,flow,cost;
};
vector<int>G[maxn];
vector<Edge>edges;
void Addedge(int x,int y,int z,int w){
Edge e;
e.from=x;e.to=y;e.cap=z;e.flow=0;e.cost=w;
edges.push_back(e);
e.from=y;e.to=x;e.cap=0;e.flow=0;e.cost=-w;
edges.push_back(e);
int c=edges.size();
G[x].push_back(c-2);
G[y].push_back(c-1);
} int s,t,totn;
int inq[maxn];
int d[maxn];
int pre[maxn];
queue<int>q;
int Spfa(int &nowflow,int &nowcost){
for(int i=1;i<=totn;++i){
inq[i]=0;d[i]=oo;
}
d[s]=0;inq[s]=1;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();inq[x]=0;
for(int i=0;i<G[x].size();++i){
Edge e=edges[G[x][i]];
if((e.cap>e.flow)&&(d[x]+e.cost<d[e.to])){
d[e.to]=d[x]+e.cost;
pre[e.to]=G[x][i];
if(!inq[e.to]){
inq[e.to]=1;
q.push(e.to);
}
}
}
}
if(d[t]==oo)return 0; int x=t,f=oo;
while(x!=s){
Edge e=edges[pre[x]];
f=min(f,e.cap-e.flow);
x=e.from;
}
nowflow+=f;nowcost+=f*d[t];
x=t;
while(x!=s){
edges[pre[x]].flow+=f;
edges[pre[x]^1].flow-=f;
x=edges[pre[x]].from;
}
return 1;
} int Mincost(){
int flow=0,cost=0;
while(Spfa(flow,cost)){
}
return cost;
} int main(){
scanf("%d",&n);
s=n+1;t=n+2;totn=t;
for(int i=1;i<=n;++i){
int m;scanf("%d",&m);
Addedge(i,t,m,0);
while(m--){
int y,z;
scanf("%d%d",&y,&z);
// Addedge(i,y,oo,z);
Addedge(s,y,1,z);
}
}
for(int i=2;i<=n;++i)Addedge(i,1,oo,0); printf("%d\n",Mincost());
return 0;
}

  

最新文章

  1. 19-ES6(2)
  2. QQ粘性布局
  3. web安全——防火墙
  4. 怎样在VS2013/MFC中使用TeeChart绘图控件
  5. python添加windows域验证
  6. 30+最佳Ajax jQuery的自动完成插件的例子
  7. 尚学堂 JAVA Day3 概念总结
  8. android获得屏幕高度和宽度
  9. [HNOI2007]紧急疏散
  10. 为什么作为下游的WSUS更新服务器总有一直处于下载状态的文件
  11. idea通过mapper快速定位到xml文件
  12. 机器学习&amp;深度学习资料收集
  13. 20171228 C#值类型和引用类型
  14. Linux 目录栈及目录切换
  15. zoj 2818 Root of the Problem(数学思维题)
  16. C# 同一应用程序域不同线程之间的参数传递方式
  17. linux下 mysql主从备份
  18. THUSC2018滚粗记
  19. mybatis的一对多,多对一,以及多对对的配置和使用
  20. JavaScript高阶函数map/reduce、filter和sort

热门文章

  1. 《Netlogo多主体建模入门》笔记4
  2. Python 2 与 3 共存了 11 年,新年就要和它道别
  3. 吴裕雄 Bootstrap 前端框架开发——Bootstrap 辅助类:关闭图标
  4. Linux之关于用户的几个重要配置文件
  5. yum出现Error downloading packages错误
  6. &#39;/&#39;和‘/*’差异造成的No mapping found for HTTP request with URI [/springMVC/welcome.jsp] in DispatcherServlet with name &#39;springmvc&#39;
  7. C++面试常见问题——13结构体与共用体的sizeof
  8. 安装ruby的一些坑
  9. 海康威视Web3.0控件个人开发经验及问题总结
  10. CVE-2019-0708 漏洞分析及相关测试