fisher最优分割法_最小二乘一定有最优解

fisher最优分割法_最小二乘一定有最优解给定一个无向图 G=(V,E),每个顶点都有一个标号,它是一个 [0,231−1] 内的整数。不同的顶点可能会有相同的标号。对每条边 (u,v),我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。现在我们知道一些顶点的标号。你需要确定余下顶点的标号使得所有边的费用和尽可能小。输入格式第一行有两个整数 N,M,N 是图的点数,M 是图的边数。接下来有 M 行,每行有两个整数 u,v,代表一条连接 u,v 的边。接下来有一个整数 K,代表已知标号的顶点个数。接下来的 K

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个无向图 G=(V,E),每个顶点都有一个标号,它是一个 [0,231−1] 内的整数。

不同的顶点可能会有相同的标号。

对每条边 (u,v),我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。

现在我们知道一些顶点的标号。

你需要确定余下顶点的标号使得所有边的费用和尽可能小。

输入格式
第一行有两个整数 N,M,N 是图的点数,M 是图的边数。

接下来有 M 行,每行有两个整数 u,v,代表一条连接 u,v 的边。

接下来有一个整数 K,代表已知标号的顶点个数。

接下来的 K 行每行有两个整数 u,p,代表点 u 的标号是 p。

假定这些 u 不会重复。

所有点编号从 1 到 N。

输出格式
输出一行一个整数,即最小的费用和。

数据范围
1≤N≤500,
0≤M≤3000,
1≤K≤N

输入样例:
3 2
1 2
2 3
2
1 5
3 100
输出样例:
97
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f;
const int N = 510;
const int M = 2 * (3000 + 500);
struct Edge{ 
   
    int v,w,next;
}edge[M];
int head[N],cnt;
int n,m,s,e;
int p[N];
void add(int u,int v,int w1,int w2){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w1;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
    edge[cnt].v = u;
    edge[cnt].w = w2;
    edge[cnt].next = head[v];
    head[v] = cnt ++;
}
int q[N],hh = 0,tt = 0,d[N],cur[N];
PII edges[M];
bool bfs(){ 
   
    hh = tt = 0;
    memset(d,-1,sizeof d);
    d[s] = 0,q[tt ++] = s,cur[s] = head[s];
    while(hh < tt){ 
   
        int t = q[hh ++];
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(d[v] == -1 && w){ 
   
                d[v] = d[t] + 1;
                cur[v] = head[v];
                q[tt ++] = v;
                if(v == e)return true;
            }
        }
    }
    return false;
}
int dfs(int u,int limit){ 
   
    if(u == e)return limit;
    int flow = 0;
    for(int i = cur[u];~i && flow < limit;i = edge[i].next){ 
   
        int v = edge[i].v,w = edge[i].w;
        cur[u] = i;
        if(d[v] == d[u] + 1 && w){ 
   
            int t = dfs(v,min(w,limit - flow));
            if(!t)d[v] = -1;
            flow += t,edge[i].w -= t,edge[i ^ 1].w += t; 
        }
    }
    return flow;
}
void build(int k){ 
   
    memset(head,-1,sizeof head);
    cnt = 0;
    for(int i = 0;i < m;i ++){ 
   
        add(edges[i].x,edges[i].y,1,1);
    }
    for(int i = 1;i <= n;i ++){ 
   
        if(p[i] >= 0){ 
   
            if((p[i] >> k) & 1)add(i,e,INF,0);      //如果要让一个点属于某s或者t,只需要从s或者t连一条向口二道门的权值为INF的边即可
            else add(s,i,INF,0);
        }
    }
}
int dinic(int i){ 
   
    build(i);
    int maxflow = 0,flow = 0;
    while(bfs())while(flow = dfs(s,INF))maxflow += flow;
    return maxflow;
}
int main(){ 
   
    cin>>n>>m;
    for(int i = 0;i < m;i ++){ 
   
        scanf("%d %d",&edges[i].x, &edges[i].y);
    }
    int k,id,x;
    s = 0,e = n + 1;
    cin>>k;
    memset(p,-1,sizeof p);
    for(int i = 1;i <= k;i ++){ 
   
        scanf("%d %d",&id,&x);
        p[id] = x;
    }
    ll ans = 0;
    for(int i = 0;i <= 30;i ++){ 
   
        ans += ((ll)dinic(i) << i);
    }
    cout<<ans<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • solr,lucene全文索引原理、结构/非结构化数据、反向索引等详细描述

    solr,lucene全文索引原理、结构/非结构化数据、反向索引等详细描述solr,lucene全文索引原理、结构/非结构化数据、反向索引等详细描述

  • linux 查看当前用户密码

    linux 查看当前用户密码用过Linux系统的人都知道,Linux系统查看用户不是会Windows那样,鼠标右键看我的电脑属性,然后看计算机用户和组即可。那么Linux操作系统里查看所有用户该怎么办呢?用命令。其实用命令就能很轻松的查看到Linux系统有哪些用户。  1、Linux里查看所有用户  (1)在终端里.其实只需要查看/etc/passwd文件就行了.  (2)看第三个参数:500以上的,就是后面建的用户了.其它则为系统的用户.  或者用cat/etc/passwd|cut-f1-d:  2、用.

  • python实现约瑟夫环问题

    python实现约瑟夫环问题#!/usr/bin/python#-*-coding:utf-8-*-definitList(n):list=[]foriinrange(n):list.append(i+1)returnlistdefrun_josephus(list,m):n=len(list)i=0j=0whilen>1:n=len(list)#.

  • 运维架构图[通俗易懂]

    运维架构图[通俗易懂]

  • scrapy+xpath爬取不可描述网站[通俗易懂]

    scrapy+xpath爬取不可描述网站[通俗易懂]今天来爬一个让人很有动力的网站,网址就不便放上来了,看看有没有有缘人能得知了还是先来items.pyimportscrapyclassAvmooItem(scrapy.Item):#definethefieldsforyouritemherelike:#name=scrapy.Field()name=scrapy.Field()

  • 基于UDP编程_udp详解

    基于UDP编程_udp详解基于UDP编程1UDP是数据报协议,无连接的,不可靠,追求传输效率的一种通信协议数据的发送和接收是同步的.在进行通信之前,不需要建立连接.其传输效率比TCP高.对其服务器而言,并没有三次握手的过程.因此和TCP相比,少了被动监听(listen)和(accept).只需要创建通信设备,绑定IP地址和端口号.然后进行数据的收发.1.服务器端的编程模型创建一个socket端点,返回该端点的文件描述符fdsocket(2)2)将fd和本地地址绑定bind(2)while(1){3)阻塞等待

发表回复

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

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