[有向图最小生成树-朱刘算法] - cool's Blog
[有向图最小生成树-朱刘算法]
做题的时候看到了这个算法，决定学习一下。
一个有向图，给定一个点，求以该点为根的最小生成树。
具体做法是这样的：先找到每个点最小的入边，如果没有环，那么这就是最小生成树。
不然就要在环中删边，并把这些环连起来。
例如点1,2形成了环，如果点3连向点，那么肯定也只能删的是（2,1）这条边。
所以可以缩点，然后缩点后的边就是原来的权值减去入点的最小入边。
递归即可。复杂度O（VE）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 2000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 110
#define M 10100
struct poi
{
double x,y;
}p[N];
struct xfy
{
int x,y;double w;
xfy(){}
xfy(int _x,int _y,double _w):x(_x),y(_y),w(_w){}
}eg[M];
int n,m,V,x,y;
double sqr(double x)
{
return x*x;
}
double dis(int x,int y)
{
return sqrt(sqr(p[x].x-p[y].x)+sqr(p[x].y-p[y].y));
}
double in[N];
int pre[N],id[N],vis[N];
double mst(int rt,int n,int m)
{
double ret = 0;
for (;;)
{
rep(i,1,n) in[i] = inf;
rep(i,1,m)
{
int x = eg[i].x,y = eg[i].y;
if (eg[i].w < in[y]) in[y] = eg[i].w,pre[y] = x;
}
rep(i,1,n)
{
if (i == rt) continue;
if (in[i] == inf) return -1;
}
int cnt = 0,len = 0; in[rt] = 0;
clr(id,0); clr(vis,0);
rep(i,1,n)
{
ret += in[i];
int x = i;
for (;vis[x] != i && !id[x] && x != rt;x = pre[x]) vis[x] = i;
if (x != rt && !id[x])
{
id[x] = ++cnt;
for (int u = pre[x];u != x;u = pre[u]) id[u] = cnt;
}
}
if (cnt == 0) return ret;
rep(i,1,n) if (!id[i]) id[i] = ++cnt;
rep(i,1,m)
{
int x = eg[i].x,y = eg[i].y;
if (id[x] == id[y]) continue;
eg[++len] = xfy(id[x],id[y],eg[i].w-in[y]);
}
rt = id[rt];
n = cnt;
m = len;
}
return ret;
}
int main()
{
for (;scanf("%d%d",&n,&m)!=EOF;V = 0)
{
rep(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y);
rep(i,1,m)
{
scanf("%d%d",&x,&y);
if (x == y) continue;
eg[++V] = xfy(x,y,dis(x,y));
}
double ans = mst(1,n,V);
if (ans < 0) puts("poor snoopy");
else printf("%.2lf\n",ans);
}
return 0;
}
[bzoj4011]一个DAG+1条s->t的边，求以1为根的生成树数量。
朱刘算法推论:DAG上的生成树数量=deg[2]*……deg[n](1为根时）
加一条边，考虑容斥即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
#define M 200010
int n,m,s,t,rd[N],deg[N],x,y;
ll inv[M],f[N],ans=1;
int h[M],last[M],head[N],l;
queue<int> q;
void add(int x,int y)
{
h[++l] = y;
last[l] = head[x];
head[x] = l;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
rep(i,1,m)
{
scanf("%d%d",&x,&y);
rd[y]++; deg[y]++;
add(x,y);
}
inv[1] = 1;
rep(i,2,m+1) inv[i] = (zhl-zhl/i)*inv[zhl%i]%zhl;
deg[t]++;
rep(i,2,n) ans = ans*deg[i]%zhl;
if (t == 1) return printf("%lld",ans),0;
rep(i,1,n) if (!rd[i]) q.push(i);
f[t] = ans;
for (;!q.empty();q.pop())
{
x = q.front();
f[x] = f[x]*inv[deg[x]]%zhl;
for (int i = head[x],y;i;i = last[i])
{
y = h[i]; f[y] = (f[y]+f[x])%zhl;
if (!--rd[y]) q.push(y);
}
}
printf("%lld\n",(ans-f[s]+zhl)%zhl);
return 0;
}
2022年8月10日 12:56
Blue host Webmail lets the individual create their professional and personalized email address. Having a business or personal brand does require a personalized email address, which increases more credibility. The attraction from customers will be more when you use your business related or personal name in the mail instead of using @outlook or @gmail. Bluehost Webmail There are options under Blue host Webmail that allow users to create personal email without actually creating a website. The Blue host Webmail control panel allows you to create multiple emails with a user-friendly option to access the same.
2025年1月20日 14:30
An incredible article you write, very very interesting and informative ... I hope you will keep writing articles as good as this, so I gained extensive insight ... thanks.!!! Feel free to visit my website
2025年1月20日 15:22
Nice post. I discover something very complicated on distinct blogs everyday. Most commonly it is stimulating to read content off their writers and use a specific thing from their store. I’d would rather apply certain with all the content on my own blog no matter whether you do not mind. Natually I’ll supply you with a link for your internet weblog. Many thanks sharing.
2025年1月20日 15:47
you’re in point of fact a good webmaster. The website loading velocity is amazing. It seems that you’re doing any distinctive trick. In addition, The contents are masterpiece. you’ve done a great activity on this subject!
2025年1月20日 16:05
The quality of the compositions you avail at Electronics Engineering Homework Help is always premium and unparalleled despite the cost being the cheapest among service providers out there. The deliveries are always before time.
2025年1月20日 16:07
Understanding the Full Form of
2025年1月20日 16:46
Students pursuing higher obstacles can be passing over easily.
2025年1月20日 16:49
Are You Looking writing.
2025年1月20日 17:12
ZenCortex is a natural supplement that helps keep your brain and for you!
2025年1月20日 17:45
Here I am sharing a wonderful platform for students in Australia , US and UK seeking , world's no1 matlab help company since 2014. They cover almost all wide range of matlab subjects, here you go:
2025年1月20日 18:43
Excellent read. I just passed this onto a colleague who was doing some research on that. He actually bought me lunch as I found it for him! Therefore let me rephrase: Thanx for lunch!
2025年1月20日 18:44
notable put up i should say and thank you for the statistics. Schooling is absolutely a sticky situation. But, is still most of the leading subjects of our time. I recognize your post and look forward to more. I just observed this weblog and feature excessive hopes for it to keep. Hold up the exquisite paintings, its tough to locate proper ones. I have added to my favorites. Thanks. Its a wonderful delight studying your publish. Its full of facts i am searching out and i love to submit a remark that "the content of your post is exquisite" notable paintings. Best publish! That is a completely best weblog that i'm able to definitively come again to more instances this year! Thank you for informative post.
2025年1月20日 18:44
exceptional study, superb website, wherein did u provide you with the statistics in this posting? I have read many of the articles on your website now, and i virtually like your fashion. Thanks a million and please preserve up the effective paintings i trully appretiate your work and recommendations given with the aid of you is beneficial to me. I will proportion this facts with my family & pals. That is a outstanding internet site, hold the high quality critiques coming. That is a excellent inspiring . I am pretty an awful lot thrilled together with your correct work. You put virtually very helpful records. I'm seeking to analyzing your subsequent put up. !!!!
2025年1月20日 18:45
What is the cash app bank name? Which bank is responsible for card issuance? New users might get confused with all these things. With the cash app team, you’ll get instant technical help so dial it when in need. Simply, pick up the phone to ask your technical issues to the technical executives of the cash app to get immediate help. Make sure to connect with helpdesk team members of the cash app for fixing issues. Also, go through our blogs from the website to know more about it.
2025年1月20日 18:45
After the onset of a stroke, you have a three-hour window of opportunity in which clot-busting drugs could save your life and reduce damage. Stroke symptoms can occur all over the body, but most strokes occur in the brain. Signs include sudden difficulty speaking or mental confusion, inability to use an arm or a leg, and facial paralysis, usually on one side. You can also have a mild stroke with less dramatic symptoms, but it's just as important to treat. As soon as you think you or someone you know might be experiencing a stroke, call 911 and at the ER ask:
2025年1月20日 18:45
This is Summit Digital Media. Our digital marketing agency provides multiple online marketing services in Kelowna with one core objective… to systematically increase your bottom line through massive growth
2025年1月20日 19:15
Here I am sharing a wonderful platform for students in Australia , US and UK seeking , world's no1 matlab help company since 2014. They cover almost all wide range of matlab subjects, here you go:
2025年1月20日 19:16
Here I am sharing a wonderful platform for students in Australia , US and UK seeking , world's no1 matlab help company since 2014. They cover almost all wide range of matlab subjects, here you go:
2025年1月20日 19:18
ZenCortex is a natural supplement that helps keep your brain and ears healthy. It uses special ingredients like Grape Seed and Green Tea to support clear thinking and good hearing. It\'s easy to take and made with plants, so it\'s safe and good for you!
2025年1月20日 19:20
Are you wandering her where the process of getting your money offarding the same, Cash App customer care executives are there to assist you out.
2025年1月20日 19:21
Besides this attribute computer. Once HP Print and Scan Doctor is open, you should click Start, and then choose your HP printer.
2025年1月20日 19:23
what i don't comprehended is in all actuality how you are not simply appreciably greater very a lot desired than you'll be at this moment. You're insightful. You notice along those strains essentially regarding the matter of this concern, delivered me as i would like to think accept as true with it is something however a fantastic deal of fluctuated factors. Its like women and men aren't blanketed besides if it is something to acquire with woman loopy! Your character stuffs wonderful. All of the time manage it up! What is taking spot i'm new to this, i coincidentally found this i've located it completely accommodating and it has assisted me with tour loads
2025年1月20日 19:26
ZenCortex is a natural supplement that helps keep your brain and ears healthy. It uses special ingredients like Grape Seed and Green Tea to support clear thinking and good hearing. It\'s easy to take and made with plants, so it\'s safe and good for you!
2025年1月20日 19:28
Venom Wallet Extension , Venom Wallet Extension has become a popular choice among crypto enthusiasts.