线切割加工报价单表格_最大费用最大流

线切割加工报价单表格_最大费用最大流[WC2007]剪刀石头布——费用流

大家好,又见面了,我是你们的朋友全栈君。

比较有思维含量的一道题

题意:给混合完全图定向(定向为竞赛图)使得有最多的三元环

三元环条件要求比较高,还不容易分开处理。

正难则反

考虑,什么情况下,三元组不是三元环

一定是一个点有2个入度,一个点有2个出度,另一个点一个入度,一个出度

也就是说,每存在一个>=2入度的点,那么会减少一些三元环

进而考虑,如果一个点有d个入度,那么减少的三元环其实是:C(d,2),即,包括它自己,再包括任意两个指向它的点(这里,a指向b,代表a能赢b),构成的三元组都不是三元环

考虑每个点作为某些个非法三元组的话,那么,

总共的三元环是:C(n,3)-∑C(du[i],2)

C(du[i],2)统计了所有与i有关的非法三元组,所以不重不漏统计完了。

 

怎样最小化这个∑?

定向,就是某些点的入度增加的过程。所以考虑某个点增加一个入度,减少的三元环的数量是多少。

即C(d+1,2)-C(d,2)=d即减少原来度数的三元环

这个减少是逐一增加的,n*(n-1)/2是下凸函数,可以考虑拆边费用流。

 

这个题的具体做法是:

把每个要定向的边看做一个点,从S到这个点连(1,0),意义是只能确定一个方向

这个点向所代表的边的两个原图端点连(1,0)的边,意义是增加入度,且只能给一个增加

每个原图 节点向T连(1,d),(1,d+1)…(1,d+n-2)的边,意义是,每增加一个入度,就会增加d的代价

最小费用最大流,spfa恰好先选择d,再选择d+1,,,,刚好符合实际的代价

最大流之后,每个边都定向完毕,而且增加的代价也都是对的。

 

至于输出方案,找每个边的代表点,看其哪一侧流量是0,就是哪一侧输。

 

代码:

#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=105; const int inf=0x3f3f3f3f; int n,s,m,t; struct node{ int nxt,to,w,v; }e[2*(N*N+N*N*2+N*N)]; int hd[N+N*N],cnt=1; void add(int x,int y,int w,int v){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].v=v; e[cnt].w=w; hd[x]=cnt; e[++cnt].nxt=hd[y]; e[cnt].to=x; e[cnt].w=0; e[cnt].v=-v; hd[y]=cnt; } int mp[N][N]; int op[N][N]; queue<int>q; bool vis[N+N*N]; int dis[N*N+N]; int incf[N*N+N],pre[N*N+N]; bool spfa(){ while(!q.empty()) q.pop(); memset(dis,inf,sizeof dis); dis[s]=0; q.push(s); pre[s]=0; incf[s]=inf; while(!q.empty()){ int x=q.front();q.pop(); vis[x]=0; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(e[i].w){ if(dis[y]>dis[x]+e[i].v){ dis[y]=dis[x]+e[i].v; pre[y]=i; incf[y]=min(incf[x],e[i].w); if(!vis[y]){ vis[y]=1; q.push(y); } } } } } if(dis[t]==inf) return false; return true; } int cos,maxflow; int du[N]; void upda(){ int x=t; while(pre[x]){ e[pre[x]].w-=incf[t]; e[pre[x]^1].w+=incf[t]; x=e[pre[x]^1].to; } cos+=incf[t]*dis[t]; maxflow+=incf[t]; } int num(int i,int j){ return n+(i-1)*(n-1)+j; } int main(){ rd(n); s=0,t=n+n*n+1; for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ rd(mp[i][j]); if(mp[i][j]==2&&i<j){ add(s,num(i,j),1,0); add(num(i,j),i,1,0); add(num(i,j),j,1,0); }else if(mp[i][j]==1){ du[j]++; } } } int ans=n*(n-1)*(n-2)/6; for(reg i=1;i<=n;++i){ ans-=du[i]*(du[i]-1)/2; for(reg j=du[i];j<=n-2;++j){ add(i,t,1,j); } } while(spfa()) upda(); ans-=cos; printf("%d\n",ans); memcpy(op,mp,sizeof mp); for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ if(mp[i][j]==2&&i<j){ int x=num(i,j); for(reg p=hd[x];p;p=e[p].nxt){ int y=e[p].to; if(y!=s&&e[p].w==0){ if(y==j){ op[i][j]=1; op[j][i]=0; }else{ op[i][j]=0; op[j][i]=1; } } } } } } for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ printf("%d ",op[i][j]); }puts(""); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/15 11:01:16 */

总结:

值得学习的是:

1.正难则反,考虑非法的三元组,这样可以通过度数直接分开计算

2.边点转化,对无向图定向、而且贡献和点的入度有关,可以尝试采取这种策略。

3.下凸函数拆边费用流。因为下凸函数,所以最小费用的时候,每次会先选择最小的,然后往右或者往左选,那么拆边,实际上真正选择的恰好也符合实际情况。

转载于:https://www.cnblogs.com/Miracevin/p/10122842.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107141.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • [生成模型新方向]: score-based generative models

    [生成模型新方向]: score-based generative models0.前言最近(2021.6)发现了生成模型的一种新的trending范式:score-basedgenerativemodel,用一句话来介绍这种结构,就是:通过在噪声扰动后的大规模数据集(noise-perturbeddatadistributions)上学习一种scorefunctions(gradientsoflogprobabilitydensityfunctions)(得分函数,一种对梯度的对数似然估计),用朗之万进行采样得到符合训练集的样本.这种新的生成模型,

  • QueryInterface详解 COM

    QueryInterface详解 COMQueryInterface接口查询IUnknown:      所有的COM接口均需要继承IUnknown接口。因此,若某个用户拥有一个IUnknown接口指针,它并不需要知道它所拥有的接口指针到底是什么类型的,而只需要通过此接口就可以用来查询其他接口就行了。      由于所有的COM接口都继承了IUnknown,每个接口的vbtl的前三项都是QueryInterface,A

  • 写java代码的软件_新手编写java代码使用什么软件

    写java代码的软件_新手编写java代码使用什么软件新手编写java代码常用的编辑器有:1、eclipseEclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。幸运的是,Eclipse附带了一个标准的插件集,包括Java开发工具(JavaDevelopmentKit,JDK)。(视频教程推荐:java视频)2、notepad++Notepad++是在微软视窗环境…

  • IntelliJ IDEA卸载与安装

    IntelliJ IDEA卸载与安装一、卸载(首次安装可跳过)导出配置运行卸载程序删除缓存&amp;配置&amp;插件卸载完成二、下载安装(一)官网:官网:http://www.jetbrains.com/idea/download/#section=windows官方文档:http://www.jetbrains.com/help/idea/meet-inte…

  • vs2012密钥_ultimate2012产品密钥

    vs2012密钥_ultimate2012产品密钥MicrosoftVisualStudioUltimate2012旗舰版有效注册密钥:YKCW6-BPFPF-BT8C9-7DCTH-QXGWC;KCW6-BPFPF-BT8C9-7DCTH-QXGWC转载于:https://www.cnblogs.com/RogerLu/p/10070312.html

    2022年10月15日
  • 概率论中常见分布总结以及python的scipy库使用:两点分布、二项分布、几何分布、泊松分布、均匀分布、指数分布、正态分布

    概率论中常见分布总结以及python的scipy库使用:两点分布、二项分布、几何分布、泊松分布、均匀分布、指数分布、正态分布

    2021年11月19日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号