BNUOJ 9870 Contestants Division
Contestants Division
This problem will be judged on UVALive. Original ID: 3694
64-bit integer IO format: %lld Java class name: Main
In the new ACM-ICPC Regional Contest, a special monitoring and submitting system will be set up, and students will be able to compete at their own universities. However there's one problem. Due to the high cost of the new judging system, the organizing committee can only afford to set the system up such that there will be only one way to transfer information from one university to another without passing the same university twice. The contestants will be divided into two connected regions, and the difference between the total numbers of students from two regions should be minimized. Can you help the juries to find the minimum difference?
Input
There are multiple test cases in the input file. Each test case starts with two integers N <tex2html_verbatim_mark>and M <tex2html_verbatim_mark>, (1N100000, 1M1000000) <tex2html_verbatim_mark>, the number of universities and the number of direct communication line set up by the committee, respectively. Universities are numbered from 1 toN <tex2html_verbatim_mark>. The next line has N <tex2html_verbatim_mark>integers; the Kth <tex2html_verbatim_mark>integer is equal to the number of students in university numbered K. The number of students in any university does not exceed 100000000. Each of the following M <tex2html_verbatim_mark>lines has two integers s <tex2html_verbatim_mark>, t <tex2html_verbatim_mark>, and describes a communication line connecting university s <tex2html_verbatim_mark>and university t <tex2html_verbatim_mark>. All communication lines of this new system are bidirectional.
N = <tex2html_verbatim_mark>0, M = <tex2html_verbatim_mark>0 indicates the end of input and should not be processed by your program.
Output
For every test case, output one integer, the minimum absolute difference of students between two regions in the format as indicated in the sample output.
Sample Input
7 6
1 1 1 1 1 1 1
1 2
2 7
3 7
4 6
6 2
5 7
0 0
Sample Output
Case 1: 1
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = ;
vector<int>g[maxn];
LL ans,cnt[maxn],sum;
int n,m,w[maxn];
bool vis[maxn];
void dfs(int u){
vis[u] = true;
cnt[u] = w[u];
LL temp;
for(int i = ,sz = g[u].size(); i < sz; i++){
if(vis[g[u][i]]) continue;
dfs(g[u][i]);
cnt[u] += cnt[g[u][i]];
if(sum - cnt[g[u][i]] >= cnt[g[u][i]])
temp = sum - *cnt[g[u][i]];
else temp = *cnt[g[u][i]] - sum;
if(temp < ans) ans = temp;
}
}
int main() {
int i,u,v,k = ;
while(~scanf("%d %d",&n,&m),n||m){
sum = ;
for(i = ; i <= n; i++){
scanf("%d",w+i);
sum += w[i];
g[i].clear();
vis[i] = false;
cnt[i] = ;
}
ans = INF;
for(i = ; i < m; i++){
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs();
printf("Case %d: %I64d\n",k++,ans);
}
return ;
}
更快的邻接表,链式前向星。。。。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = ;
struct arc{
int to,next;
};
LL ans,cnt[maxn],sum;
int n,m,w[maxn],head[maxn],tot;
bool vis[maxn];
arc g[maxn*];
void add(int u,int v){
g[tot].to = v;
g[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u){
vis[u] = true;
cnt[u] = w[u];
LL temp;
for(int i = head[u]; i != -; i = g[i].next){
if(vis[g[i].to]) continue;
dfs(g[i].to);
cnt[u] += cnt[g[i].to];
if(sum - cnt[g[i].to] >= cnt[g[i].to])
temp = sum - *cnt[g[i].to];
else temp = *cnt[g[i].to] - sum;
if(temp < ans) ans = temp;
}
}
int main() {
int i,u,v,k = ;
while(~scanf("%d %d",&n,&m),n||m){
sum = ;
tot = ;
for(i = ; i <= n; i++){
scanf("%d",w+i);
sum += w[i];
head[i] = -;
vis[i] = false;
cnt[i] = ;
}
ans = INF;
for(i = ; i < m; i++){
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
dfs();
printf("Case %d: %I64d\n",k++,ans);
}
return ;
}
最新文章
- C#类型转换运算符之 explicit implicit
- Repository设计模式
- Neo4j 两种索引Legacy Index与Schema Index区别
- phalcon: queueing使用心得,需要安装相应的软体
- mongoDB 用java连接
- android 引用 project以及下拉刷新开源类库Android-PullToRefresh 的使用
- WAD Forwarder版USB Loader的安装和运行
- 视频(其他)下载+tomcat 配置编码+图片上传限制大小
- Broadcast Reveiver作用
- 一个Python小白5个小时爬虫经历
- java 计算源码的行数
- Eureka restTemplate访问超时
- PAT (Basic Level) Practice (中文)1023 组个最小数
- DateTime时间格式转换为Unix时间戳格式
- vCenter机器查找功能不可用的解决
- 【Mac使用系列】【转载】十几个Mac实用工具
- How Not to Crash #2: Mutation Exceptions 可变异常(不要枚举可变的集合)
- C C++ 文件输入与输出
- NET技术公众号已上线
- jquery ui导入两次的错误提示
热门文章
- [UOJ388]配对树
- [BZOJ1453]Dface双面棋盘
- ACM_素数环(dfs)
- Linux环境下HDFS集群环境搭建关键步骤
- 用.NetReactor保护您的源码[转][修改]
- Oracle报错:“ORA-18008: 无法找到 OUTLN 方案 ”的解决方案
- 12.1Java-构造方法
- bootstrap不同屏幕区分数值
- hihocoder offer收割编程练习赛10 C 区间价值
- CF792C Divide by Three