Java 解法, 执行用时: 281ms, 内存消耗: 18968K, 提交时间: 2021-10-01 23:33:10

import java.util.*;

public class Main {
    static int[] head, neighbor, next, w, R, t;
    static int N, idx;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while (T-- > 0) {
            R = new int[25];
            for (int i = 1; i < 25; i++) R[i] = cin.nextInt();
            N = cin.nextInt();
            t = new int[25];
            for (int i = 0; i < N; i++) t[cin.nextInt() + 1]++;
            boolean flag = false;
            for (int i = 0; i <= 1000; i++) {
                if (spfa(i)) {
                    flag = true;
                    System.out.println(i);
                    break;
                }
            }
            if (!flag) System.out.println("No Solution");
        }
    }
    
    static boolean spfa(int s24) {
        build(s24);
        int[] dist = new int[25];
        Arrays.fill(dist, -0x3f3f3f3f);
        boolean[] visited = new boolean[25];
        int[] cnt = new int[25];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        dist[0] = 0;
        visited[0] = true;
        while (!queue.isEmpty()) {
            int t = queue.poll();
            visited[t] = false;
            for (int i = head[t]; i != -1; i = next[i]) {
                int j = neighbor[i];
                if (dist[j] < dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if (cnt[j] >= 25) return false;
                    if (!visited[j]) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
        }
        return true;
    }
    
    static void build(int s24) {
        idx = 0;
        head = new int[25];
        Arrays.fill(head, -1);
        neighbor = new int[75];
        next = new int[75];
        w = new int[75];
        for (int i = 1; i <= 24; i++) {
            add(i - 1, i, 0);
            add(i, i - 1, -t[i]);
        }
        for (int i = 8; i <= 24; i++) add(i - 8, i, R[i]);
        for (int i = 1; i <= 7; i++) add(i + 16, i, -s24 + R[i]);
        add(0, 24, s24);
        add(24, 0, -s24);
    }
    
    static void add(int a, int b, int c) {
        neighbor[idx] = b;
        w[idx] = c;
        next[idx] = head[a];
        head[a] = idx++;
    }
}

C++ 解法, 执行用时: 20ms, 内存消耗: 428K, 提交时间: 2022-05-17 09:56:48

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
int head[N];
struct node{
    int v,w,nxt;
}e[4*N];
int n,m,k,cnt;
int vis[N],dis[N],num[N];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
bool spfa(){
    memset(dis,-0x3f,sizeof(dis));
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(0);
    vis[0]=1;
    dis[0]=0;
    while(!q.empty()){
        int now=q.front();
        vis[now]=0;
        q.pop();
        for(int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v]<dis[now]+e[i].w){
                dis[v]=dis[now]+e[i].w;
                if(!vis[v]) {
                    q.push(v);
                    vis[v]=1;
                    num[v]=num[now]+1;
                    if(num[v]>24) return false;
                }
            }
        }
    }
    return true;
}
int t,r[30],nums[30],ans[30];
signed main(){
  cin>>t;
  while(t--){
    memset(nums,0,sizeof(nums));
    for(int i=1;i<=24;i++) scanf("%lld",&r[i]);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
      int x;
      scanf("%lld",&x);
      nums[x+1]++;
    }
    bool flag=false;
    for(int k=0;k<=1000;k++){
      memset(head,0,sizeof(head));
      memset(e,0,sizeof(e));
      cnt=0;
      add(0,24,k);
      add(24,0,-k);
      for(int i=1;i<=24;i++) {
        add(i-1,i,0);
        add(i,i-1,-nums[i]);
      }
      for(int i=8;i<=24;i++) add(i-8,i,r[i]);
      for(int i=1;i<=7;i++){
        add(i+16,i,r[i]-k);
      }
      if(spfa()) { flag=true; cout<<k<<endl; break; }
    }
    if(flag==false) cout<<"No Solution"<<endl;
  }
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 16ms, 内存消耗: 496K, 提交时间: 2020-01-04 16:39:34

#include<bits/stdc++.h>
using namespace std;

//T = partial_sum(T);
struct Edge {
  int u, v, w;
};
vector<Edge> edges;
int dis[25];
int main() {
  int TC; cin >> TC;
  while (TC--) {
    vector<int> R(24); for (auto &r: R) cin >> r;
    int N; cin >> N;
    vector<int> T(24);
    for (int i = 0; i < N; i++) {
      int x; cin >> x;
      T[x]++;
    } 
    int ans = -1;
    for (int x23 = 0; x23 <= N; x23++) {
      memset(dis, 0x8f, sizeof(dis));
      edges.clear();
      edges.push_back(Edge{0, 1, T[0]});
      for (int i = 1; i <= 23; i++) edges.push_back(Edge{i + 1, i, -T[i]});
      for (int i = 1; i <= 24; i++) edges.push_back(Edge{i - 1, i, 0});
      for (int i = 8; i < 24; i++) edges.push_back(Edge{i+1-8, i+1, R[i]});
      for (int i = 0; i < 8; i++) edges.push_back(Edge{i+1+16, i+1, R[i] - x23});

      dis[0] = 0;
      bool isOk = true;
      for (int i = 0; i <= 25; i++) {
        isOk = true;
        for (auto &e: edges) {
          if (dis[e.v] < dis[e.u] + e.w) {
            dis[e.v] = dis[e.u] + e.w;
            isOk = false;
          }
        }
        if (isOk) break;
      }
      if (isOk) {
        ans = x23;
        break;
      }
    }
    if (ans == -1) cout << "No Solution" << endl;
    else cout << ans << endl;
  }
}