#include <iostream>
#include <cstdio>
#include <limits.h>
using namespace std;
// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
// Number of vertices in the graph
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[], int V)
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[], int n,int V)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d tt %d\n", i, dist[i]);
}
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[][500], int src, int V, int s[][500])
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet, V);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v]&& graph[u][v] != (-1))
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
for(int i = 0; i < V; i++)
{
s[src][i] = dist[i];
}
}
float score_cover(const int ele[],const int cost, const int cover[], int eleCnt)
{
int count = 0;
float result = 10001;
for(int i = 0; i < eleCnt; i++)
{
if(cover[i] == 1 && ele[i] == 0)
count++;
}
if(count != 0)
result = cost / count;
return result;
}
float score_satisfy(const int ele[], const int cost, const int sat[],const int pop[] , int
eleCnt)
{
int count = 0;
int population_sum = 0;
float result = 10001;
for(int i = 0; i < eleCnt; i++)
{
if(sat[i] == 1 && ele[i] == 0)
population_sum += pop[i];
}
if(population_sum != 0)
result = cost / population_sum;
return result;
}
int main()
{
int n, B, t1, t2;
int population[1000] = {0};
int cost[1000] = {0};
int graph[500][500] = {{0}};
int s[500][500] = {0};
float score_c = 0;
float score_s = 0;
int cover[500][500] = {0}; // 記錄若蓋某村莊有無覆蓋其它村莊
int satisfy[500][500] = {0};// 記錄若蓋在某村有無滿足他村
int choose[500] = {0};
int elecov[500] = {0}; // 某村有無被覆蓋
int elesat[500] = {0};// 某村有無被滿足
int output[500] = {0};
int firsttime = 1;
int outputCount = 0;
int costlimit = 0;
cin >> n >> B >> t1 >> t2;
for(int i = 0; i < n; i++)
{
cin >> population[i];
}
for(int i = 0; i < n; i++)
{
cin >> cost[i];
}
for(int i = 0; i < n; i++)
{
graph[i][i] = 0;
for(int j = i + 1; j < n; j++)
{
cin >> graph[i][j];
graph[j][i] = graph[i][j];
}
}
for(int i = 0; i < n; i++)
{
dijkstra(graph, i, n, s);
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(s[i][j] <= t1)
cover[i][j] = 1;
if(s[i][j] <= t2)
satisfy[i][j] = 1;
}
}
for(int i = 0; i < n; i++)
{
int count = 0;
int x = 0;
for(int j = 0; j < n; j++)
{
if(s[i][j] > t1)
count++;
}
if(count == (n - 1))
{
choose[i] = 1;
output[outputCount] = i;
outputCount++;
elecov[i] = 1;
elesat[i] = 1;
}
else if(count == (n - 2))
{
for(int j = 0; j < n; j++)
{
if(s[i][j] <= t1 && i != j)
x = j;
}
choose[x] = 1;
output[outputCount] = x;
outputCount++;
for(int j = 0; j < n; j++)
{
if(cover[x][j] == 1)
elecov[j] = 1;
if(satisfy[x][j] == 1)
elesat[j] = 1;
}
}
}
int stop = 0;
int cost_sum = 0;
while(stop != n)
{
float min = 10001;
float second = 10002; //v2
int k = 0;
int k_s = 0;
for(int i = 0; i < n; i++)
{
if(choose[i] != 1)
{
score_c = score_cover(elecov, cost[i], cover[i], n);
if(min > score_c)
{
second = min;
min = score_c;
k = i;
}
else if(second > score_c)
second = score_c;
k_s = i;
}
}
int popk = 0; int popk_s = 0;
for(int i = 0; i < n; i++)
{
if(satisfy[k][i] == 1 && elesat[i] == 0)
popk += population[i];
if(satisfy[k_s][i] == 1 && elesat[i] == 0)
popk_s += population[i];
}
if(popk_s > popk && (cost[k_s] / cost[k]) <= 1.2)
k = k_s;
choose[k] = 1;
output[outputCount] = k;
outputCount += 1;
cost_sum += cost[k];
for(int i = 0; i < n; i++)
{
if(cover[k][i] == 1)
elecov[i] = 1;
if(satisfy[k][i] == 1)
elesat[i] = 1;
}
stop = 0;
for(int i = 0; i < n; i++)
{
if(elecov[i] == 1)
stop++;
}
}
int remain = B - cost_sum;
// bool satstop = 1;
while(remain > 0)
{
int count_A = 0;
int count_B = 0;
for(int i = 0; i < n; i++)
{
if(choose[i] == 0)
{
count_A++;
if(cost[i] > remain)
count_B++;
}
}
if(count_A == count_B)
break;
float min = 10001;
int k = 0;
for(int i = 0; i < n; i++)
{
if(choose[i] == 0 && cost[i] <= remain)
{
score_s = score_satisfy(elesat, cost[i], satisfy[i], population, n);
if(min > score_s)
{
min = score_s;
k = i;
}
}
}
choose[k] = 1; //也要把 elesat 設 1
output[outputCount] = k;
outputCount++;
remain -= cost[k];
for(int i = 0; i < n; i++)
{
if(satisfy[k][i] == 1)
elesat[i] = 1;
}
} //output
for(int i = 0; i < outputCount; i++)
{
if(firsttime == 1)
{
cout << output[i] + 1;
firsttime = 0;
}
else
{
cout << " " << output[i] + 1;
}
}
return 0;
}
前置動作：
a.根據 Dijkstra 演算法得到的各點間最短距離，可以得到各點覆蓋（cover[i][j]）及滿足
（satisfy[i][j]）的關係。
cover[i][j]: 若 i 到 j 的距離小於等於 t1，表示 i 覆蓋 j，值設為 1，反之為 0。
satisfy[i][j]: 若 i 到 j 的距離小於等於 t2，表示 i 滿足 j，值設為 1，反之為 0。
b.寫兩個函數分別是 score_cover（計算每多覆蓋一個村莊所需要的成本）及 score_satisfy
（計算每多滿足一個人所需要的成本），
輸入分別為（記錄村莊是否已被覆蓋的陣列, 該村的成本, 該村覆蓋哪些村莊, 總村莊數
n）及（記錄村莊是否已被滿足的陣列, 該村的成本, 該村滿足哪些村莊, 人口, 總村莊
數 n）
作法：
score_cover: 傳入一個村莊，迴圈從 i=0 到 n-1，每次檢查如果此村莊有覆蓋 i 村，且 i
村還沒被覆蓋過，就計數 1 次，將成本除以計算出的總次數。
score_satisfy: 傳入一個村莊，迴圈從 i=0 到 n-1，每次檢查若此村有滿足 i 村，且 i 村還
沒被滿足，那就把 i 村的人數累加起來，最後將成本除以總人數。
分三個步驟求解：
1.
先找出必須要選擇的村莊（該村莊為沒有其它村莊到此村莊的時間小於 t1，意即只有自
己包含自己的村莊），先選擇這類型的村莊，將這些村莊設定為已選取，且已被包含和
滿足。
2.
再把剩下村莊依據 CP 值（多包含一個村莊所需的成本）作選取，直到覆蓋所有村莊。
作法：若是該村沒有被選，則呼叫 score_cover 函數計算 cp 值，選取值最小的村莊，
並將它已覆蓋及滿足的村莊記錄為 1，迴圈直到所有村莊皆被覆蓋為止，並計算已花費
的總成本。
3.
檢查預算是否還有剩下，若有，則再依據 CP 值（多滿足一個人所需要的成本）作選取，
直到預算不足為止。
作法：若該村還沒被選，則呼叫 score_satisfy 函數計算 cp 值，選取值最小的村莊，檢
查他的成本有沒有比剩餘的預算還大，若是有，則排除此村後，再重跑迴圈，若是無，
就選取該村，並將它已覆蓋及滿足的村莊記為 1，迴圈執行直到預算不夠為止。最後，
印出所有選取的村莊。