编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China 头条阅读 学淘股 China Travel
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> POJ 2987 Firing -> 正文阅读

[C++]POJ 2987 Firing

Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 10804   Accepted: 3263
Description
You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do some firings. You’re now simply too mad to give response to questions like “Don’t you think it is an even more stupid decision to have signed them?”, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings’ underlings’ underlings… An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?
Input
The input starts with two integers n (0 < n ≤ 5000) and m (0 ≤ m ≤ 60000) on the same line. Next follows n + m lines. The first n lines of these give the net profit/loss from firing the i-th employee individually bi (|bi| ≤ 107, 1 ≤ i ≤ n). The remaining m lines each contain two integers i and j (1 ≤ i, j ≤ n) meaning the i-th employee has the j-th employee as his direct underling.
Output
Output two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.
Sample Input

5 5
8
-9
-20
12
-10
1 2
2 5
1 4
3 4
4 5

Sample Output

2 2

Hint
As of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.
Source
POJ Monthly--2006.08.27, frkstyc
这道题的性质和上一道题差不多,
都是最大闭合权图,
不同的地方在于
1.m的取值与权值无关,这样的话我们让读入的x,y之前的边为INF就好
2.需要求人数,我们重新DFS一遍残余网络,如果这条边还有流量的话,说明需要裁掉这个人,至于为什么,https://wenku.baidu.com/view/986baf00b52acfc789ebc9a9.html
注意几个问题:
1.不要全开long long会超时
2.输出的数不要写反了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #define lli long long int 
  7 using namespace std;
  8 const int MAXN=2000001;
  9 const int INF = 1e8;
 10 inline void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 15     n=flag==1?-x:x;
 16 }
 17 int n,m,s,t;
 18 struct node
 19 {
 20     int u,v,flow,nxt;
 21 }edge[MAXN];
 22 int head[MAXN];
 23 int cur[MAXN];
 24 int num=0;
 25 int deep[MAXN];
 26 lli tot=0;
 27 bool vis[MAXN];
 28 lli out;
 29 void add_edge(int x,int y,int z)
 30 {
 31     edge[num].u=x;
 32     edge[num].v=y;
 33     edge[num].flow=z;
 34     edge[num].nxt=head[x];
 35     head[x]=num++;
 36 }
 37 void add(int x,int y,int z)
 38 {
 39     add_edge(x,y,z);
 40     add_edge(y,x,0);
 41 }
 42 bool BFS()
 43 {
 44     memset(deep,0,sizeof(deep));
 45     deep[s]=1;
 46     queue<int>q;
 47     q.push(s);
 48     while(q.size()!=0)
 49     {
 50         int p=q.front();
 51         q.pop();
 52         for(int i=head[p];i!=-1;i=edge[i].nxt)
 53             if(!deep[edge[i].v]&&edge[i].flow)
 54                 deep[edge[i].v]=deep[edge[i].u]+1,
 55                 q.push(edge[i].v);
 56     }
 57     return deep[t];
 58     
 59 }
 60 lli DFS(int now,int nowflow)
 61 {
 62     if(now==t||nowflow<=0)
 63         return nowflow;
 64     lli totflow=0;
 65     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
 66     {
 67         if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
 68         {
 69             int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
 70             edge[i].flow-=canflow;
 71             edge[i^1].flow+=canflow;
 72             totflow+=canflow;
 73             nowflow-=canflow;
 74             if(nowflow<=0)
 75                 break;
 76         }
 77     
 78     }
 79     return totflow;
 80 }
 81 void Dinic()
 82 {
 83     lli ans=0;
 84     while(BFS())
 85     {
 86         memcpy(cur,head,MAXN);
 87         ans+=DFS(s,1e8);
 88     }
 89     out=tot-ans;
 90 }
 91 int find_pep(int now)
 92 {
 93     vis[now]=1;
 94     for(int i=head[now];i!=-1;i=edge[i].nxt)
 95         if(!vis[edge[i].v]&&edge[i].flow)
 96             find_pep(edge[i].v);
 97 }
 98 int main()
 99 {
100     //freopen("a.in","r",stdin);
101     //freopen("c.out","w",stdout);
102     while(~scanf("%d%d",&n,&m))
103     {
104         memset(head,-1,sizeof(head));
105         num=0;
106         s=0,t=n+1;
107         tot=0;
108         for(int i=1;i<=n;i++)
109         {
110             int a;read(a);
111             if(a>0)    tot+=a,add(s,i,a);
112             if(a<0) add(i,t,-a);
113         }
114         for(int i=1;i<=m;i++)
115         {
116             int x,y;read(x);read(y);
117             add(x,y,INF);
118         }
119         Dinic();
120         memset(vis,0,sizeof(vis));
121         int ans=0;
122         find_pep(s);
123         for(int i=1;i<=n;i++)
124             ans+=vis[i];
125         //cout<<ans<<" "<<out<<endl;
126         printf("%d %I64d\n",ans,out);
127     }
128     return  0;
129 }

  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章      下一篇文章      查看所有文章
加:2017-08-10 23:21:30  更:2017-08-10 23:21:46 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 三丰软件 开发 中国文化 阅读网 头条阅读 学淘股 China Travel 日历 万年历 2020年1日历
2020-1-22 0:40:31
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识