注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2647  

2013-03-03 19:31:50|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:有n个员工,m条需求,每一条需求给出a和b员工,表示a员工的工资要比b的高,每名员工的最低工资888,问在满足所有条件下,老板最少需要多少钱,如果不能满足则输出-1。
题解:
建立有向图,因为已知的是a比b大,所以存储边的时候要反过来存;
后利用拓扑排序计算出每名员工需多发的工资之和,最后加上888*n,实现如下:
每次将所有入度为0的点找出并删去,则这些点代表的员工应多发的工资为当前遍历次数减一。
要是图中存在环就返回-1。
例如有这样一个有向图:
1 -> 2 -> 3 <- 4
第一次遍历,搜出所有入度为0的点为1和4,于是1和4上标为0(1-1),然后删除1和4;
第二次遍历,搜出所有入度为0的点为2,于是2上标为1(2-1),然后删除2;
第三次遍历,搜出所有入度为0的点为3,于是3上标为2(3-1),然后删除3;
遍历结束,各个点之和为0+0+1+2,最后加上888*4。

/*
* test.cpp
*
* Created on: 2013-03-03
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 10010
int n,g[N][22];//数据量大,g改用邻接表
int ru[N];

int toposort()
{
int j,t,k,flag,temp,sum,s[N],vis[N];
memset(s,0,sizeof(s));
t=0;temp=0;sum=0;
while(t<n)
{
flag=0;
memset(vis,0,sizeof(vis));//需要借助vis数组实现,找到一个入度为0的点后,之后遍历的时候不可以访问从该点出发的所有点,因为那些点当然的入度不为1(如例子中,找到入度为0的点1,赋值完删除后,之后遍历时,不可以对2进行访问,因为2在这一遍遍历中入度不为1)
for(j=1;j<=n;j++)
{
if(!vis[j] && ru[j]==0)
{
t++;
flag=1;
ru[j]--;
s[j]=s[j]>temp?s[j]:temp;
sum+=s[j];
for(k=1;k<=g[j][0];k++)
{
ru[g[j][k]]--;
vis[g[j][k]]=1;
}
}
}
temp++;
if(flag==0)
return -1;
}
return sum;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int m,a,b,t,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
g[i][0]=0;//第一列记录各行的个数
memset(ru,0,sizeof(ru));
while(m--)
{
scanf("%d%d",&b,&a);
g[a][++g[a][0]]=b;
ru[b]++;
}
t=toposort();
if(t!=-1)
printf("%d\n",888*n+t);
else
printf("-1\n");
}
return 0;
}



  评论这张
 
阅读(97)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018