@[【http://noi.openjudge.cn/】4.3算法之圖論——1538:Gopher II]
題目
查看提交統計提問
總時間限制: 2000ms 內存限制: 65536kB
描述
The gopher family, having averted the canine threat, must face a new predator.
The are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.
輸入
The input contains several cases. The first line of each case contains four positive integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances are in metres; all times are in seconds; all velocities are in metres per second.
輸出
Output consists of a single line for each case, giving the number of vulnerable gophers.
樣例輸入
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0
樣例輸出
1
翻譯
**題目：**地鼠II
描述：
地鼠家族在避免了犬科動物的威脅后，必須面對一個新的捕食者。
有n個地鼠洞和m個地鼠洞，每個洞都位于不同的（x，y）坐標處。一只鷹來了，如果地鼠在s秒內沒有到達一個洞，它很容易被吃掉。一個洞最多只能救一只地鼠。所有的地鼠都以相同的速度奔跑。地鼠家族需要一種逃生策略，以盡量減少易受攻擊的地鼠數量。
輸入：
輸入包含幾個案例。每種情況的第一行包含四個小于100的正整數：n、m、s和v。接下來的n行給出地鼠的坐標；以下m線給出了地鼠洞的坐標。所有距離均以米為單位；所有時間均以秒為單位；所有速度均以米每秒為單位。
輸出：
輸出由每種情況的單行組成，給出了易受攻擊的地鼠數量。
例如：
在語言模型中，編碼器和解碼器都是由一個個的 Transformer 組件拼接在一起形成的。
代碼
#include <bits/stdc++.h>
using namespace std;
struct point {double x, y;int id,oid;vector<point*> h;point() { x = 0; y = 0;oid=0;}//成員要初始化，否則會"runtime error" point(int idx, double px, double py) : id(idx), oid(0), x(px), y(py) {}
}one[210];
bool k[210];
int n, m, s, v,ans;
double x, y;
void view(int x,point* p){cout<<x<<endl;cout<<"坐標"<<p->x<<","<<p->y<<endl; cout<<"可達目標：\n";for(vector<point*>::iterator i=p->h.begin();i!=p->h.end();i++)cout<<"("<<(*i)->x<<","<<(*i)->y<<")\t";cout<<"選中"<<p->oid<<endl;
}
void view(){for(int i=n+1;i<=n+m;i++){cout<<i<<"坐標"<<one[i].x<<","<<one[i].y<<"\t"<<"達"<<one[i].oid<<endl; } cout<<endl;
}
bool go(point *p){//該老鼠能否找到洞__匈牙利算法，進行二分圖匹配 for(vector<point*>::iterator i=p->h.begin();i!=p->h.end();i++){//該老鼠能達的洞 if(k[(*i)->id])continue;//該洞已經用過了 k[(*i)->id]=1;//標記該洞，此老鼠不能再用該洞了 if(!(*i)->oid||go(&one[(*i)->oid])){//該洞沒用過或者該洞本來的老鼠可以找到別的洞 (*i)->oid=p->id;//該洞被該老鼠占用 return 1;}}return 0;
}
int main() {//freopen("data.cpp", "r", stdin);while(cin >> n >> m ){//題目講The input contains several cases. 有多組數據 ans=0; memset(one, 0, sizeof(one));cin>> s >> v;for (int i = 1; i <=n; i++) {//遍歷每個老鼠 cin >> x >> y; one[i] = point(i,x,y);}for (int i = 1; i <=m; i++) {//遍歷每個鼠洞 cin >> x >> y; one[n+i] = point(n+i, x,y );for (int j = 1; j <=n; j++) {//遍歷每個老鼠 double xg = one[j].x, yg = one[j].y;if ((x - xg)* (x - xg) + (y - yg)* (y - yg) <= (s * v)* (s * v)){//看哪些老鼠可以跑進哪個洞 one[n+i].h.push_back(&one[j]);//該老鼠可以跑到該洞 one[j].h.push_back(&one[n+i]);//該洞成為該老鼠的一個選項 }} }for (int i = 1; i <=n; i++){//遍歷每個老鼠 memset(k,0,sizeof(k));//清空深搜標記 if(go(&one[i]))ans++;//判定該老鼠能否找到洞 //view(i,&one[i]);//view();}//view();cout << n-ans<<endl; }return 0;
}
細節
- 題目說有多組數據，The input contains several cases。
- 結構體內元素一定要初始化，否則會提示runtime error
struct point {double x, y;int id,oid;vector<point*> h;point() { x = 0; y = 0;oid=0;}//成員要初始化，否則會"runtime error" point(int idx, double px, double py) : id(idx), oid(0), x(px), y(py) {}
}one[210];
-在結構體內，每個老鼠可以躲藏的洞可以用指針描述，堅決落實。
deep seek對過程進行的分析：
初始狀態
老鼠：
老鼠 1：(0.0, 3.0)
老鼠 2：(0.0, 2.0)
老鼠 3：(0.0, 1.0)
鼠洞：
鼠洞 1：(0.0, 51.0)（未占用）
鼠洞 2：(0.0, 52.0)（未占用）
鼠洞 3：(0.0, 53.0)（未占用）
匹配結果：ans = 0
步驟 1：匹配老鼠 1
老鼠 1嘗試匹配：
嘗試鼠洞 1：
鼠洞 1 未占用，直接匹配。
匹配成功！
更新狀態：
鼠洞 1 被老鼠 1 占用。
ans = 1。
步驟 2：匹配老鼠 2
老鼠 2嘗試匹配：
嘗試鼠洞 1：
鼠洞 1 已被老鼠 1 占用，無法直接匹配。
遞歸調用：嘗試為老鼠 1 尋找其他鼠洞。
遞歸過程：
老鼠 1 嘗試鼠洞 2：
鼠洞 2 未占用，直接匹配。
匹配成功！
更新狀態：
鼠洞 1 被老鼠 2 占用。
鼠洞 2 被老鼠 1 占用。
ans = 2。
步驟 3：匹配老鼠 3
老鼠 3嘗試匹配：
嘗試鼠洞 1：
鼠洞 1 已被老鼠 2 占用，無法直接匹配。
遞歸調用：嘗試為老鼠 2 尋找其他鼠洞。
遞歸過程：
老鼠 2 嘗試鼠洞 2：
鼠洞 2 已被老鼠 1 占用，無法直接匹配。
遞歸調用：嘗試為老鼠 1 尋找其他鼠洞。
老鼠 1 嘗試鼠洞 3：
鼠洞 3 未占用，直接匹配。
匹配成功！
更新狀態：
鼠洞 1 被老鼠 3 占用。
鼠洞 2 被老鼠 2 占用。
鼠洞 3 被老鼠 1 占用。
ans = 3。
最終狀態
匹配結果：
老鼠 1 → 鼠洞 3
老鼠 2 → 鼠洞 2
老鼠 3 → 鼠洞 1
最終答案：ans = 3
算法
一群老鼠避難，在一堆洞里找藏身處（一洞一老鼠，老鼠只能在規定時間跑到一部分洞里），求最優化，就是更多的老鼠能找到洞。這種兩個集合配對問題就是二分圖問題。
思路就是找洞，如果該洞被占有了，煩請它去找別的洞（增廣路徑），找不到就不挪窩，找到了就挪。
這就是最早是由兩位匈牙利數學家 Dénes K?nig 和 Jen? Egerváry 在 20 世紀 30 年代提出的匈牙利算法。
