“浪潮杯”第九届山东省ACM大学生程序设计竞赛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int maxn=510;
const int INF=0x3f3f3f3f;
int n,vis[maxn],mp[maxn][maxn],tmp[maxn][maxn],link[maxn];
int cnt=0;

bool match(int x){
    for(int i=1;i<=n;i++){
        if(!vis[i]&&tmp[x][i]){
            vis[i]=1;
            if(link[i]==-1||match(link[i])){
                link[i]=x;
                return true;
            }
        }
    }
    return false;
}

int hungry(){
    memset(link,-1,sizeof(link));
    int tot=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(match(i))
            tot++;
    }
    return tot;
}

bool check(int x){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]<x) tmp[i][j]=0;
            else tmp[i][j]=mp[i][j];
        }
    }

    int res=hungry();
    if(res==cnt) return true;
    else return false;
}

int main(){
    scanf("%d",&n);
    int l=INF,r=-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&mp[i][j]);
            tmp[i][j]=mp[i][j];
            l=min(l,mp[i][j]);
            r=max(r,mp[i][j]);
        }
    }

    cnt=hungry();  //最多杀害的怪物的数量
    //cout<<"cnt="<<cnt<<endl;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%dn",l);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
int main()
{
    int t,n,a;
    scanf("%d",&t);
    while(t--){
       long long sum=0,mx=INF;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a);
            sum+=a;
            if(a<mx)
                mx=a;
        }
        sum+=(n-2)*mx;
        printf("%lldn",sum);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,fa[maxn],pre[maxn],num[maxn],power[maxn];
vector<int> son[maxn];
int value[maxn],leaf[maxn],cnt;

/*
dfs()时间复杂度分析：
	对于具有n个顶点、e条边的图来说，dfs算法对图中的每个顶点最多调用一次，因此其递归调用总次数为n。当访问某个
顶点v时，dfs的时间主要花在从该顶点出发查找它的邻接点上。当用邻接表表示图时，需要遍历该顶点的所有邻接点，所有dfs
的总时间为O(n+e);当用邻接矩阵表示图时，需要遍历该顶点行的所有元素，所以dfs的总时间为O(n^2). 
*/

//对于树来说，e=n-1。用邻接表存储树，所以，dfs时间复杂度为O(n) 

void dfs(int id,int w){   //找到叶节点以及每条路径完成每次升级获得到的能量 
	value[id]=w;
	if(son[id].size()==0){
		leaf[cnt++]=id;
		return ;
	}
	int len=son[id].size();
	for(int i=0;i<len;i++){
		int x=son[id][i];
		//printf("power[%d]=%dn",x,power[x]);
		dfs(x,w+power[x]);
	}
}

bool cmp(int a,int b){
	return value[a]>value[b];
}

int previs(int x,int w){
    if(x==0) return w;
    if(num[x]==0)	return 0;
    if(num[x]<w){w=num[x];num[x]=0;}
    else num[x]-=w;
    return previs(fa[x],w);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&fa[i],&num[i],&power[i]);
		son[fa[i]].push_back(i);
	}
	
	dfs(0,0); 
	
	/*for(int i=0;i<cnt;i++){
		printf("%d %dn",leaf[i],value[leaf[i]]);
	}*/
	sort(leaf,leaf+cnt,cmp);
	
	ll ans=0;
	int min_num;
	for(int i=0;i<cnt;i++){  //cnt条路径，由路径value[]从大到小进行求能量值 
		int x=leaf[i];
		min_num=previs(x,num[x]); //注意：这里求每段路径的最小手轴数用递归来求，递推的话会超时
		ans+=1ll*min_num*value[x];
	}
	
	/*
	//超时 
	for(int i=0;i<cnt;i++){  //cnt条路径，由路径value[]从大到小进行求能量值 
		int x=leaf[i];
		min_num=num[x];
		int y=fa[x]; 
		while(y){
			min_num=min(min_num,num[y]);
			y=fa[y];
		}
		ans+=1ll*min_num*value[x];
		
		if(min_num){
			y=x;
			while(y){
				num[y]-=min_num;
				y=fa[y];
			}
		}
	}
	
	*/
	
	printf("%lldn",ans);
	return 0;
}