How Many to Be Happy?
时间:2022-03-13 20:22
How Many to Be Happy?
时间限制: 1 Sec 内存限制: 128 MB题目描述
Let G be a connected simple undirected graph where each edge has an associated weight. Let’s consider the popular MST (Minimum Spanning Tree) problem. Today, we will see, for each edge e, how much modification on G is needed to make e part of an MST for G. For an edge e in G, there may already exist an MST for G that includes e. In that case, we say that e is happy in G and we define H(e) to be 0. However, it may happen that there is no MST for G that includes e. In such a case, we say that e is unhappy in G. We may remove a few of the edges in G to make a connected graph G′ in which e is happy. We define H(e) to be the minimum number of edges to remove from G such that e is happy in the resulting graph G′.Figure E.1. A complete graph with 3 nodes. Consider the graph in Figure E.1. There are 3 nodes and 3 edges connecting the nodes. One can easily see that the MST for this graph includes the 2 edges with weights 1 and 2, so the 2 edges are happy in the graph. How to make the edge with weight 3 happy? It is obvious that one can remove any one of the two happy edges to achieve that.
Given a connected simple undirected graph G, your task is to compute H(e) for each edge e in G and print the total sum.
输入
Your program is to read from standard input. The first line contains two positive integers n and m, respectively, representing the numbers of vertices and edges of the input graph, where n ≤ 100 and m ≤ 500. It is assumed that the graph G has n vertices that are indexed from 1 to n. It is followed by m lines, each contains 3 positive integers u, v, and w that represent an edge of the input graph between vertex u and vertex v with weight w. The weights are given as integers between 1 and 500, inclusive.输出
Your program is to write to standard output. The only line should contain an integer S, which is the sum of H(e) where e ranges over all edges in G.样例输入
3 3 1 2 1 3 1 2 3 2 3
样例输出
1
来源/分类
ICPC 2017 Daejeon
最小生成树的MST性质的应用。我们想让某一条边一定是最小生成树中的边,只要找到任意一种点集的分配,使得这条边的两个顶点在不同的分配中且边权是连接这两个分配的所有边中最小的那一个。显然只有边权比它小的边才会影响它是不是在最小生成树中。于是我们可以只在图中保留边权小于当前边权的边,看看是否能找到一种点集的分配。显然当这个边的两个顶点在新图中仍然连通时,我们找不到这种分配,于是就需要砍掉若干边使两顶点不连通,于是题目就转化为了最小割问题。 参考博客:
#include<bits/stdc++.h> #define INF LLONG_MAX/2 #define N 505 using namespace std; struct ss { int v,next; long long flow; }; int head[N],now_edge=0,S,T; ss edg[N*2]; void init() { now_edge=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,long long flow) { edg[now_edge]=(ss){v,head[u],flow}; head[u]=now_edge++; edg[now_edge]=(ss){u,head[v],flow}; head[v]=now_edge++; } int dis[N]; int bfs() { memset(dis,0,sizeof(dis)); queue<int>q; q.push(S); dis[S]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edg[i].next) { ss &e=edg[i]; if(e.flow>0&&dis[e.v]==0) { dis[e.v]=dis[now]+1; q.push(e.v); } } } if(dis[T]==0)return 0; return 1; } int current[N]; long long dfs(int x,long long maxflow) { if(x==T)return maxflow; for(int i=current[x];i!=-1;i=edg[i].next) { current[x]=i; ss &e=edg[i]; if(e.flow>0&&dis[e.v]==dis[x]+1) { long long flow=dfs(e.v,min(maxflow,e.flow)); if(flow!=0) { e.flow-=flow; edg[i^1].flow+=flow; return flow; } } } return 0; } long long dinic() { long long ans=0,flow; while(bfs()) { for(int i=0;i<N;i++)current[i]=head[i]; while(flow=dfs(S,INF))ans+=flow; } return ans; } int from[N],to[N],w[N]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d %d",&from[i],&to[i],&w[i]); } int ans=0; for(int i=1;i<=m;i++) { init(); for(int j=1;j<=m;j++) if(w[j]<w[i])addedge(from[j],to[j],1); S=from[i]; T=to[i]; ans+=dinic(); } printf("%d\n",ans); return 0; }View Code
相关推荐
- Android系统编程入门系列之界面Activity交互响应
- 新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- uni-app滚动视图容器(scroll-view)之监听上拉事件
- uniapp h5,app两端复制文本
- Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn
- 诺基亚短信生成!太好玩了
- iOS 跳转App Store进行评分
- 开发一个即时通讯App
- 关闭苹果IOS app自动更新
电脑软件
本类排行
- 1关闭苹果IOS app自动更新
- 2iOS 跳转App Store进行评分
- 3诺基亚短信生成!太好玩了
- 4Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 5uniapp h5,app两端复制文本
- 6uni-app滚动视图容器(scroll-view)之监听上拉事件
- 7新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- 8Android系统编程入门系列之界面Activity交互响应
- 9开发一个即时通讯App
- 10【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn