题意:给你一个有趣图的定义:在这个图中有一个根,根与每个点都有边和回边,除了根之外,其他的点的出度和入度都为2,然后给你一个图让你经过几步操作可以使此图变为有趣图,操作为:删边或者加边。

思路:枚举根,然后删除与根有关的边,重新建图,用二分图求最大匹配,可以用匈牙利算法,加的边数:满足题中有关根的加边数+(点数-匹配数),删掉的边数:边数-满足题中有关根的使用的边数-匹配时使用的边数。

 #include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf=<<; int g[][];
int n,m;
bool chk[];
int match[];
vector<int>x[]; int dfs(int p)
{
for(int i=; i<(int)x[p].size(); i++)
{
int v=x[p][i];
if(!chk[v])
{
chk[v]=true;
int t=match[v];
match[v]=p;
if(t==-||dfs(t))
{
return ;
}
match[v]=t;
}
}
return ;
} int Pro(int c)
{
memset(match,-,sizeof(match));
int res=;
for(int i=; i<=n; i++)
{
if(i==c) continue;
memset(chk,false,sizeof(chk));
res+=dfs(i);
}
return res;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
vector<int>gg[];
for(int i=; i<=m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
gg[u].push_back(v);
g[u][v]=;
}
int ans=inf;
for(int i=; i<=n; i++)
{
int t1=n-gg[i].size();
for(int j=; j<=n; j++)
{
if(!g[j][i]) t1++;
}
if(g[i][i]==) t1--;
for(int j=; j<=n; j++)
{
x[j].clear();
}
int cnt=;
for(int j=; j<=n; j++)
{
if(j==i) continue;
for(int k=; k<(int)gg[j].size(); k++)
{
int v=gg[j][k];
if(v==i)continue;
cnt++;
x[j].push_back(v);
}
}
ans=min(ans,t1+cnt+n--*Pro(i));
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. spring websocket源码分析续Handler的使用
  2. 湖南省第十二届大学生计算机程序设计竞赛 B 有向无环图 拓扑DP
  3. BZOJ2164 : 采矿
  4. uniGUI试用笔记(十四)TUniTreeView的CheckBox
  5. 李洪强-C语言7-C语言运算符
  6. SQL server 创建 修改表格 及表格基本增删改查 及 高级查询 及 (数学、字符串、日期时间)函数[转]
  7. js实现文字字幕滚动
  8. 垃圾回收(GC)的三种基本方式
  9. JQ 一些基本方法
  10. 利用json获取天气信息
  11. 常见的java设计模式
  12. Nginx+IIS简单的部署
  13. 初学Vue 遇到Module not found:Error:Can`t resolve &#39;less-loader&#39; 问题
  14. [Machine Learning] some concept about the CV
  15. redis面试必问
  16. JAVA-部署-摘
  17. POJ 2583
  18. OpenCV&amp;&amp;python_图像平滑(Smoothing Images)
  19. WWDC 2017 苹果开发者大会
  20. Git笔记——01

热门文章

  1. js中子页面父页面方法 变量相互调用
  2. java时间类型的转换/获取当前时间/将时间转换成String/将String转换成时间
  3. pdo mysql错误:Cannot execute queries while other unbuffered queries are active
  4. 配置ipvsadm服务
  5. 在Entity Framework 4.0中使用 Repository 和 Unit of Work 模式
  6. ios工程中ARC与非ARC的混合
  7. spring + Quartz定时任务配置
  8. window7电脑设置好了,却无法远程?
  9. Docker快速入门
  10. 变量声明declare,简单运算符运算,变量测试与内容替换
  11. Java的访问权限详解(3+1)public private protected default
  12. (爬虫)requests库
  13. Redis非关系型数据库
  14. 高性能HTTP加速器Varnish-3.0.3搭建、配置及优化步骤
  15. python_14 多态,封装
  16. JVM总结-虚拟机怎么执行字节码
  17. 8.17 纯css画一个着重号图标
  18. scapy学习笔记(5)
  19. Eclipse 离线汉化的方法
  20. C++ 数组复制