D、Bulbasaur

The input starts with one line containing exactly one integer T, which is the number of test cases.

For each test case, the first line contains three integers n, m and k, indicating the number of face photos, the number of body photos, and the number of existing association edges, respectively.

Then followed by k lines, each consists of three integers a_i, b_i and c_i, representing an edge weighted c_i connecting the a_i-th face photo with the b_i-th body photo.

- 1 ≤ T ≤ 5.
- 1 ≤ n, m, k ≤10⁵.
- 1 ≤ a_i ≤ n.
- 1 ≤ b_i ≤ m.
- 1 ≤ c_i ≤ 10⁹.
- $\forall i\not=j\to(a_i\not=a_j\lor b_i\not=b_j)$ .

C++14(g++5.4) 解法, 执行用时: 446ms, 内存消耗: 868K, 提交时间: 2018-08-04 12:40:36

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,i,n,m,k,x,y,z,p=0;
	cin>>t;
	int b[100005],sum;
	while(t--)
	{
		p++;
		long long sum=0;
		memset(b,0,sizeof(b));
		cin>>n>>m>>k;
		for(i=1;i<=k;i++)
		{
			    cin>>x>>y>>z;
				if(z>b[y])
				{
					sum-=b[y];
					sum+=z;
					b[y]=z;
				}
		}
	  printf("Case #%d: %lld\n",p,sum);
	}
}

pypy3 解法, 执行用时: 1425ms, 内存消耗: 37348K, 提交时间: 2022-07-13 14:05:23

T = int(input())
for _ in range(1, T + 1):
    n, m, k = list(map(int, input().split()))
    mx = {}
    for __ in range(k):
        a, b, c = list(map(int, input().split()))
        if b not in mx:
            mx[b] = c
        mx[b] = max(mx[b], c)
    ans = sum(mx.values())
    print('Case #{}: {}'.format(_, ans))

Python3(3.5.2) 解法, 执行用时: 1480ms, 内存消耗: 14140K, 提交时间: 2018-08-05 15:23:27

from collections import defaultdict
for _ in range(int(input())):
    n, m, k = map(int, input().split())
    d = defaultdict(int)
    for i in range(k):
        a, b, c = map(int, input().split())
        d[b] = max(d[b], c)
    print('Case #%d: %d' %(_ + 1, sum(d.values())))

C++11(clang++ 3.9) 解法, 执行用时: 565ms, 内存消耗: 1004K, 提交时间: 2019-02-21 15:55:06

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int c=1;c<=n;c++)
	{
		int a[100005]={0};
		long long p,q,k,v,s=0;
		cin>>p>>q>>k;
		while(k--)
		{
			cin>>p>>q>>v;
			if(a[q]<v)s-=a[q]-v,a[q]=v;
		}
		cout<<"Case #"<<c<<": "<<s<<endl;
	}
}

详情