题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4514
他都给你说了是匹配，那肯定是二分图匹配啦！
考虑可以整除，除完之后还是个质数，那么质因数的个数（不是种类）肯定是一奇一偶
于是建成二分图跑一跑MCMF()就行啦！
当然如果你比较刚烈，想跑带权带花树肯定也是可以的啦！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 200+9;
const int N = 100000+9;
const int MX = 100000;
const int INF = 0x7fffffff;
int pri[N],tot,vis[N],n,A[M],B[M],C[M];
int lft[M],rit[M],tl,tr,sur[M],S,T,inq[M];
int head[M],nxt[N],to[N],flow[N];
LL cost[N],dis[M];
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void Get_Prime_Number(){
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++tot] = i;
for (int j=1;j<=tot&&i*pri[j]<=MX;j++)
if (i%pri[j]) vis[i*pri[j]] = 1;
else {vis[i*pri[j]] = 1; break;}
}
}
inline void Add_Edge(int u, int v, int f, LL c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
inline bool divide(int w) {int ret = 0; for (int i=1;i<=tot;i++) while (w%pri[i] == 0) w /= pri[i], ret++; return ret&1;}
inline bool is_prime(int w) {for (int i=1;i<=tot;i++) if (pri[i] >= w) break; else if (w%pri[i] == 0) return false; return true;}
inline bool SPFA(){
memset(dis,127,sizeof(dis));
que.push(S); inq[S] = 1; dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
} return dis[T] < dis[M-2];
}
inline LL MCMF(){
LL ret = 0, tot_cost = 0; bool tag=1;
for (int w=T,f;SPFA()&&tag;w=T) {
for (f=INF;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
if (dis[T]*f+tot_cost > 0) ret += -tot_cost / dis[T], tag = 0;
else {
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret += f; tot_cost += f*dis[T];
}
} return ret;
}
int main(){
n = read(); Get_Prime_Number(); S = 0; T = M - 1;
for (int i=1;i<=n;i++) A[i] = read();
for (int i=1;i<=n;i++) B[i] = read();
for (int i=1;i<=n;i++) C[i] = read();
for (int i=1;i<=n;i++)
if (divide(A[i])) lft[++tl] = i, Add_Edge(S,i,B[i],0);
else rit[++tr] = i, Add_Edge(i,T,B[i],0);
for (int i=1;i<=tl;i++) for (int j=1;j<=tr;j++) {
int w1 = A[lft[i]], w2 = A[rit[j]]; if (w1 > w2) swap(w1, w2);
if (w2 % w1 == 0 && is_prime(w2 / w1))
Add_Edge(lft[i],rit[j],INF,-1LL*C[lft[i]]*C[rit[j]]);
} printf("%lld\n",MCMF());
return 0;
}
For most recent information you have to go to see
web and on internet I found this website as
a most excellent web site for most recent updates.
I have been exploring for a bit for any high quality articles or weblog posts in this kind of area .
Exploring in Yahoo I finally stumbled upon this site. Reading this information So i’m glad
to exhibit that I’ve a very excellent uncanny feeling I came upon exactly what I needed.
I most certainly will make sure to don?t put out of your mind this site and give it a look regularly.
Your means of describing all in this piece of writing is
actually pleasant, all can effortlessly understand it, Thanks a lot.
When someone writes an article he/she keeps the thought of a
user in his/her brain that how a user can be aware of it.
Therefore that’s why this article is great. Thanks!
Hi I am so happy I found your weblog, I really found you by mistake, while I was
researching on Yahoo for something else, Regardless I am here now and would just like to say cheers for a remarkable post and
a all round enjoyable blog (I also love the theme/design), I don’t have time to browse it all at the minute but I have book-marked it and also included your RSS feeds, so when I
have time I will be back to read a great deal
more, Please do keep up the fantastic work.
It’s remarkable to pay a quick visit this site and reading the views of all colleagues concerning this post,
while I am also zealous of getting know-how.
Excellent article. Keep writing such kind of information on your blog.
Im really impressed by your blog.
Hi there, You’ve performed an excellent job.
I will definitely digg it and in my view recommend to my friends.
I’m sure they will be benefited from this web site.
Appreciating the hard work you put into your website
and detailed information you provide. It’s awesome to come across a blog every once in a while that
isn’t the same unwanted rehashed information. Great read!
I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.
What’s up to every body, it’s my first visit of this blog; this blog contains awesome and in fact excellent material in favor of visitors.
It’s going to be end of mine day, but before end I
am reading this wonderful article to increase my knowledge.
Outstanding quest there. What happened after?
Thanks!
This is my first time pay a visit at here and i am
genuinely happy to read everthing at one place.
If some one wishes expert view about blogging and site-building afterward i suggest him/her to pay a quick visit this weblog, Keep
up the pleasant job.
Remarkable! Its really remarkable paragraph, I have got much clear
idea regarding from this post.
Very nice article, totally what I needed.
A fascinating discussion is definitely worth comment. There’s no doubt that that you
need to publish more about this subject matter, it
may not be a taboo matter but typically folks don’t talk about such topics.
To the next! All the best!!
I always spent my half an hour to read this blog’s posts all the time along with a cup of coffee.
pof natalielise
I do not even know how I ended up here, but I thought this post was good.
I don’t know who you are but certainly you’re going to a famous blogger if you
are not already 😉 Cheers!
Keep on working, great job!
This is really interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more
of your excellent post. Also, I have shared your
website in my social networks!
Hey would you mind stating which blog platform you’re working with?
I’m planning to start my own blog soon but I’m having a tough
time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different
then most blogs and I’m looking for something unique.
P.S Sorry for being off-topic but I had to ask!
I want to to thank you for this wonderful read!!
I absolutely enjoyed every bit of it. I have got you bookmarked to look
at new stuff you post…
Thank you a lot for sharing this with all people you really realize what you are speaking
about! Bookmarked. Kindly additionally visit my website =).
We may have a link alternate arrangement between us
Cool blog! Is your theme custom made or did you download it
from somewhere? A design like yours with a few simple adjustements
would really make my blog stand out. Please let me know where
you got your design. Bless you
Right here is the right website for everyone who really
wants to understand this topic. You realize so much its almost hard to
argue with you (not that I actually would want to…HaHa).
You certainly put a fresh spin on a topic which has been discussed
for a long time. Wonderful stuff, just wonderful!
I do not know if it’s just me or if perhaps everyone else encountering issues with your site.
It looks like some of the text within your content are running off the screen. Can someone else please comment and let me know if this is
happening to them as well? This could be a issue with my web
browser because I’ve had this happen before. Thank
you
Appreciation to my father who told me regarding this blog, this webpage is truly awesome.
If you are going for finest contents like me, only visit this
website daily for the reason that it gives feature contents, thanks
Hello there, just became aware of your blog through Google, and found
that it’s truly informative. I am gonna watch out for brussels.
I’ll be grateful if you continue this in future. Many people will be benefited from your
writing. Cheers!
What’s up colleagues, pleasant paragraph and fastidious urging commented here,
I am actually enjoying by these.
When someone writes an article he/she retains the idea of a user in his/her mind that how a user can know it.
Thus that’s why this piece of writing is outstdanding.
Thanks!
I was wondering if you ever thought of changing the structure of your blog?
Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so
people could connect with it better. Youve got an awful lot of
text for only having 1 or two pictures. Maybe you could space it out better?
It’s wonderful that you are getting ideas from this article as
well as from our argument made at this place.
Hi there! This article couldn’t be written any better!
Reading through this post reminds me of my previous roommate!
He constantly kept preaching about this. I am going to send this post to him.
Fairly certain he’s going to have a good read.
I appreciate you for sharing!
Fantastic goods from you, man. I have understand your stuff previous to and you’re just too fantastic.
I really like what you have acquired here, certainly like what you are saying and the way
in which you say it. You make it entertaining and you still care for to keep it sensible.
I can’t wait to read far more from you. This is really a tremendous
site.
Thank you for any other informative blog.
The place else may I get that type of information written in such an ideal approach?
I’ve a project that I’m just now running on, and I’ve been on the look
out for such information.
Write more, thats all I have to say. Literally, it
seems as though you relied on the video to make
your point. You clearly know what youre talking about,
why throw away your intelligence on just posting videos to your blog when you could be giving us something informative to read?
Thanks for sharing your info. I really appreciate your efforts
and I will be waiting for your further write ups thanks once again.
I got this web site from my pal who told me concerning this
site and now this time I am browsing this site and reading very informative articles or reviews at this
place.
This is a topic which is near to my heart… Best wishes! Where are your contact
details though?
Hi to every one, it’s truly a nice for me to pay a quick visit this web page, it contains useful Information.
What’s up, always i used to check webpage posts here early in the morning,
because i like to gain knowledge of more and
more.
Hi there i am kavin, its my first occasion to commenting anywhere, when i read this
post i thought i could also make comment due to this brilliant article.
I’m impressed, I must say. Seldom do I encounter a
blog that’s both equally educative and entertaining,
and let me tell you, you’ve hit the nail on the head. The issue is
something too few men and women are speaking intelligently about.
Now i’m very happy I stumbled across this in my
hunt for something regarding this.
I am really enjoying the theme/design of your weblog.
Do you ever run into any web browser compatibility problems?
A handful of my blog readers have complained about my blog not operating correctly in Explorer
but looks great in Chrome. Do you have any ideas to help fix this problem?
Undeniably consider that which you stated.
Your favorite reason seemed to be on the net the simplest
factor to be aware of. I say to you, I certainly get
annoyed whilst people consider issues that they just do not know about.
You controlled to hit the nail upon the highest as neatly
as outlined out the whole thing with no need side effect , people can take a signal.
Will probably be again to get more. Thanks
It’s a shame you don’t have a donate button! I’d without
a doubt donate to this superb blog! I suppose for now i’ll settle for book-marking and adding
your RSS feed to my Google account. I look forward to new
updates and will share this blog with my Facebook group.
Chat soon!
I have read so many content about the blogger lovers but this article is genuinely
a pleasant post, keep it up.
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time
a comment is added I get four emails with the same comment.
Is there any way you can remove people from that service?
Many thanks!
For most recent information you have to pay a visit world wide web and on internet I
found this web site as a best site for newest updates.
Howdy! I’m at work browsing your blog from my new iphone!
Just wanted to say I love reading through your blog and look forward to all your posts!
Keep up the outstanding work!
I was recommended this website by my cousin. I am not sure whether this post is written by him
as nobody else know such detailed about my problem.
You are wonderful! Thanks!
Your style is very unique compared to other folks I have read stuff from.
Thanks for posting when you have the opportunity, Guess I will just bookmark
this blog.
My brother recommended I might like this website.
He was totally right. This post actually made my day.
You can not imagine just how much time I had spent
for this info! Thanks!
Spot on with this write-up, I truly believe this web site needs much more attention. I’ll probably
be back again to read more, thanks for the advice!
I like it whenever people come together and share thoughts.
Great website, stick with it!
Thanks for any other informative website. The place else may just I get that kind of information written in such a perfect method?
I have a challenge that I am simply now running on, and I’ve been at the
look out for such information.
I do accept as true with all of the concepts you’ve introduced for your post.
They’re really convincing and can certainly work. Still,
the posts are very brief for novices. May just you please extend them a little from
subsequent time? Thank you for the post.
My spouse and I stumbled over here different website and thought I may as well check things out. I like what I see so now i am following you. Look forward to checking out your web page again.
Pretty! This has been a really wonderful article. Thank
you for supplying this info.
Someone necessarily lend a hand to make seriously posts I’d state.
This is the very first time I frequented your website page and
so far? I amazed with the analysis you made to create this particular
submit incredible. Fantastic task!
This piece of writing is actually a pleasant one it assists new the web viewers,
who are wishing in favor of blogging.
Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times it’s hard to get that “perfect balance” between usability and visual appeal.
I must say you’ve done a amazing job with this. In addition, the blog loads very
fast for me on Firefox. Exceptional Blog!
My developer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using WordPress on a number of websites for about a year and am nervous about switching to another platform.
I have heard very good things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any help would be really appreciated!
I all the time used to read article in news
papers but now as I am a user of web thus from now I
am using net for posts, thanks to web.
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you!
However, how could we communicate?
I was curious if you ever considered changing the layout of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content
so people could connect with it better. Youve
got an awful lot of text for only having one or two
pictures. Maybe you could space it out better?
You’re so awesome! I do not suppose I’ve read something like this before.
So wonderful to find somebody with original thoughts on this subject.
Really.. many thanks for starting this up.
This web site is one thing that is needed on the web, someone with a bit of originality!
Hi there, i read your blog occasionally and i own a similar one and i was just wondering
if you get a lot of spam comments? If so how do you protect against it,
any plugin or anything you can suggest? I get so much lately it’s
driving me insane so any assistance is very much appreciated.
I have been browsing online more than 3 hours today, yet I never found
any interesting article like yours. It’s pretty
worth enough for me. In my opinion, if all site owners and bloggers made good content as you did, the net will
be a lot more useful than ever before.
What¦s Going down i am new to this, I stumbled upon this I have found It positively useful and it has helped me out loads. I hope to contribute & help different customers like its aided me. Good job.
Thank you so much pertaining to giving us an update on this matter
on your web site. Please know that if a new post appears or in the event
that any improvements occur about the current posting, I would be interested
in reading a lot more and focusing on how to make good
utilization of those approaches you discuss. Thanks for your time and consideration of other folks by making your blog available.
Hello! I’m at work surfing around your blog from my new apple iphone!
Just wanted to say I love reading your blog and look forward to all your posts!
Carry on the superb work!
531862 566755Hello, Neat post. There is actually a dilemma along with your internet site in internet explorer, could test thisK IE nonetheless could be the marketplace leader and a large portion of men and women will leave out your exceptional writing due to this dilemma. 98920
I think the admin of this site is actually working hard in favor of his web
site, because here every information is quality based material.