HDU 6005 Pandaland(无向图最小环)
题意：
给出无向图，然后求最小环，点较多，边<=4000。
思路：
求最小环，对于n较少的题floyd改版来解决，而这题点很多而边不是很多，所以只能通过枚举每一条边，然后再求去掉这条边之后，其两个端点之间的最短路，从而来寻找最小环，时间复杂度为O(m*m*logn)。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 8005;
const int bas = 20001;
struct node {
int v; ll w;
bool operator<(const node k)const {
return w > k.w;
}
};
priority_queue<node> q;
struct node1 {ll w; int u, v, next;} edge[maxn];
int no, head[maxn];
ll dis[maxn];
bool col[maxn], vis[maxn];
unordered_map<int, int> has;
int t, m, n;
void init()
{
no = 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v, ll w)
{
edge[no].u = u;
edge[no].v = v;
edge[no].w = w;
edge[no].next = head[u];
head[u] = no++;
}
ll DJ(int S, int T)
{
memset(vis, 0, sizeof vis);
while(!q.empty()) q.pop();
memset(dis, 0x3f3f, sizeof dis);
dis[S] = 0;
q.push((node){S, 0});
while(!q.empty())
{
node tp = q.top(); q.pop();
int u = tp.v;
if(u == T) return dis[T];
if(vis[u]) continue;
vis[u] = 1;
for(int k = head[u]; k+1; k = edge[k].next)
{
if(col[k]) continue;
int v = edge[k].v;
if(dis[v] > dis[u]+edge[k].w)
{
dis[v] = dis[u]+edge[k].w;
q.push((node){v, dis[v]});
}
}
}
return inf;
}
void work()
{
ll ans = inf;
memset(col, 0, sizeof col);
for(int i = 0; i < no; i+=2)
{
int u = edge[i].u, v = edge[i].v;
col[i] = col[i+1] = 1;
ll _dis = DJ(u, v);
if(_dis+edge[i].w < ans) ans = _dis+edge[i].w;
col[i] = col[i+1] = 0;
}
if(ans == inf) puts("0");
else printf("%lld\n", ans);
}
int main()
{
scanf("%d", &t);
for(int _ = 1; _ <= t; ++_)
{
init();
n = 0; has.clear();
scanf("%d", &m);
for(int i = 1; i <= m; ++i)
{
int _x1, _y1, _x2, _y2, w, u, v;
scanf("%d %d %d %d %d", &_x1, &_y1, &_x2, &_y2, &w);
_x1 += 10000, _y1 += 10000, _x2 += 10000, _y2 += 10000;
if(has.find(_x1*bas+_y1) == has.end())
has[_x1*bas+_y1] = u = ++n;
else
u = has[_x1*bas+_y1];
if(has.find(_x2*bas+_y2) == has.end())
has[_x2*bas+_y2] = v = ++n;
else
v = has[_x2*bas+_y2];
add(u, v, w);
add(v, u, w);
}
printf("Case #%d: ", _);
work();
}
return 0;
}
继续加油~