2021/1/9 流量

2023.1.25 PM 06:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=f606
出題者 : 2021年1月APCS
標籤 : 模擬法
難易度 : 2

解題想法 : 
這題是個很複雜的實作題，但只要依照題目需求小心的實作，就能夠打敗此題。

※注意 : 就算是大於1000的流量，第1~1000的每單位仍然是收3元，請特別注意這點。

//C++ language

#include<iostream>
#include<vector> //vector
#include<algorithm> //min_element() 
using namespace std;
int main(){
    int n,m,k; cin>>n>>m>>k;
    vector<int> flow[n],ANS;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int x; cin>>x;
            flow[i].push_back(x);
        }
    }
    for(int i=0;i<k;i++){
        vector<int> router[m],plan(n);
        for(int &p:plan) cin>>p;
        for(int j=0;j<n;j++) 
            router[plan[j]].push_back(j);
        int ans=0;
        for(int from=0;from<m;from++){
            for(int to=0;to<m;to++){
                int sum_flow=0;
                if(router[from].size()==0) continue;
                for(int j:router[from]) sum_flow+=flow[j][to];
                if(from==to) ans+=sum_flow;
                else{
                    if(sum_flow<=1000) ans+=sum_flow*3;
                    else ans+=3000+(sum_flow-1000)*2;
                }
            }
        }
        ANS.push_back(ans);
    }
    cout<<*min_element(ANS.begin(),ANS.end())<<"\n";
    return 0;
}

## Python language

n,m,k=map(int,input().split())
flow=[]
for i in range(n): flow.append([int(x) for x in input().split()])
ANS=[]
for i in range(k):
    router=[[] for _ in range(m)]
    plan=[int(x) for x in input().split()]
    for j in range(n): router[plan[j]].append(j)
    ans=0
    for From in range(m):
        for To in range(m):
            if From==To:
                sum_flow=0
                if router[From]==[]: continue
                sum_flow += sum([flow[i][To] for i in router[From]])
                ans+=sum_flow
            else:
                sum_flow=0
                if router[From]==[]: continue
                sum_flow += sum([flow[i][To] for i in router[From]])
                if sum_flow<=1000: ans+=sum_flow*3
                elif sum_flow>1000: ans+=3000+(sum_flow-1000)*2
    ANS.append(ans)
print(min(ANS))

相關文章

分享此文：