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

线切割加工报价单表格_最大费用最大流[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)


相关推荐

  • 织梦中data文件夹是存放什么内容的

    织梦中data文件夹是存放什么内容的

  • 喵友黎言卓:一个人的创业战争「建议收藏」

    喵友黎言卓:一个人的创业战争「建议收藏」大二选择辍学创业,没有团队、没有资金,个人生活极其窘困。这个站长还能坚持多久?24岁的创业者黎言卓,想做一款既带有社交与分享功能,但又与SNS不同;既可以写博客,却又与传统博客、轻博客、微博不同的产品。描述这款产品似乎有些拗口,总之,这个身处广州、在校期间被同学为电脑“天才”的年青人,2010年一个人编程、创办了一个叫“喵友”的博客社区。目前它已经有大约9000名用户,且每月以千人的数量在增长…

  • javascript trim_stripslashes()函数的作用

    javascript trim_stripslashes()函数的作用[code="java"]通过PHP验证表单数据我们要做的第一件事是通过PHP的htmlspecialchars()函数传递所有变量。在我们使用htmlspecialchars()函数后,如果用户试图在文本字段中提交以下内容:location.href(‘http://www.hacked.com’)-代码不会执行,因为会被保存为转义代码,就像这样:&…

  • arduino 超声波测距误差较大_超声波测距的背景

    arduino 超声波测距误差较大_超声波测距的背景arduino实现超声波测距涉及模块:四线超声波测距模块,LCD1602ALCD1602连接实验代码:#include<LiquidCrystal.h>LiquidCrystallcd(12,11,5,4,3,2);constintTrigPin=7;constintEchoPin=6;floatcm;voidsetup(){lcd.begin(16,2);pinMode(TrigPin,OUTPUT);pinMode

  • Linux中用tar命令对文件夹进行打包压缩

    Linux中用tar命令对文件夹进行打包压缩一、打包的概念     打包:指将多个文件(或目录)合并成一个文件,方便在不同节点之间传递或在服务器集群上部署。     压缩或打包文件常见扩展名    *.tar,*.tar.gz,*.gz,*.bz2,*.Z;     Linux系统一般文件的扩展名用途不大,但是压缩或打包文件的扩展名时必须的,因为linux支持的压缩命令较多,不同的压缩技术使…

发表回复

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

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