Codechef 12.4 CONNECT 随机化+斯坦纳树
Codechef 14.9 QRECT CDQ分治+分治+线段树

Codechef 14.12 RIN 网络流+最小割

shinbokuow posted @ Dec 02, 2015 08:51:41 PM in Something with tags 网络流 最小割 , 1961 阅读

 

题目大意:
有$n$个课程,$m$个学期,每个课程都必须选择在某个学期学习,第$i$个课程在第$j$个学期学习将会得到$X_{i,j}$的价值。同时有$k$个限制条件,第$i$个限制条件给定$A_{i},B_{i}$,要求课程$A_{i}$所在的学期必须在$B_{i}$所在的学期之前。
求所有课程价值的最大平均值。
数据范围$n,m,k\leq{100}$,$0\leq{X_{i,j}}\leq{100}$,保证至少存在一种合法的解。
算法讨论:
将每个课程拆成一条长度为$m+1$的链,分别表示第$0-m$个学期,对于课程$i$,第$j-1(1\leq{j}\leq{m})$个点到第$j$个点连一条边,容量为$100-X_{i,j}$。
对于源点,连向所有链的第$0$个学期,容量为$\infty$。
所有链的第$m$个学期连向汇点,容量为$\infty$。
对于限制$A,B$,对于$1\leq{i}\leq{m}$,从$A$链的第$i-1$个学期连向$B$链的第$i$个学期,容量为$\infty$,这样就能满足题目中的限制了。
于是我们求最小割,再用$100\times{n}$减去就是最大的总和了。
再除以$n$就是最大平均值。
时空复杂度:
时间复杂度$O(MaxFlow(n\times{m},(n+k)\times{m}))$,空间复杂度$O((n+k)\times{m})$。
代码:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

#define inf 0x3f3f3f3f
struct Solver {
	static const int V = 100010;
	static const int E = 1000010;
	int head[V], nxt[E], flow[E], to[E], ind, d[V];
	void reset() {
		ind = 0;
		memset(head, -1, sizeof head);
	}
	void addedge(int a, int b, int c) {
		int q = ind++;
		to[q] = b;
		nxt[q] = head[a];
		head[a] = q;
		flow[q] = c;
	}
	void make(int a, int b, int c) {
		addedge(a, b, c);
		addedge(b, a, 0);
	}
	bool bfs(int s, int t, int l, int r) {
		static int q[V], fr, ta, i, j;
		for (i = l; i <= r; ++i)
			d[i] = -1;
		fr = ta = 0;
		d[q[ta++] = s] = 0;
		while (fr != ta) {
			i = q[fr++];
			for (j = head[i]; j != -1; j = nxt[j])
				if (flow[j] && d[to[j]] == -1)
					d[q[ta++] = to[j]] = d[i] + 1;
		}
		return d[t] != -1;
	}
	int dinic(int p, int t, int Maxflow) {
		if (p == t)
			return Maxflow;
		int last = Maxflow;
		for (int j = head[p]; j != -1; j = nxt[j]) {
			if (flow[j] && d[to[j]] == d[p] + 1) {
				int toflow = dinic(to[j], t, last > flow[j] ? flow[j] : last);
				if (toflow) {
					flow[j] -= toflow;
					flow[j ^ 1] += toflow;
					if (!(last -= toflow))
						return Maxflow;
				}
			}
		}
		d[p] = -1;
		return Maxflow - last;
	}
	int Maxflow(int s, int t, int l, int r) {
		int ans = 0;
		while (bfs(s, t, l, r))
			ans += dinic(s, t, inf);
		return ans;
	}
}g;

int node[110][110];
int main() {
	int n, m, k, x, a, b;
	cin >> n >> m >> k;
	int i, j, id = 0;
	for (i = 1; i <= n; ++i)
		for (j = 0; j <= m; ++j)
			node[i][j] = ++id;
	g.reset();
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			cin >> x;
			if (x == -1)
				g.make(node[i][j - 1], node[i][j], inf);
			else
				g.make(node[i][j - 1], node[i][j], 100 - x);
		}
	}
	int s = 0, t = ++id;
	for (i = 1; i <= n; ++i) {
		g.make(s, node[i][0], inf);
		g.make(node[i][m], t, inf);
	}
	while (k--) {
		cin >> a >> b;
		for (i = 1; i <= m; ++i)
			g.make(node[a][i - 1], node[b][i], inf);
	}
	
	printf("%.2lf\n", (n * 100 - g.Maxflow(s, t, 0, id)) / (double)n);
	
	return 0;
}

 

Emma 说:
Jan 18, 2023 07:31:55 PM

RIN network flow is a technique for finding the maximum flow in a network. It is based on the idea of finding the path of least resistance in the network. The algorithm starts at a source node and greedily selects the path with the least resistance to the sink node. The path is then Censoring porn added to the final solution. This process is repeated until all paths have been considered or the maximum flow has been found. RIN also has the ability to find the minimum cut in a network. This is the minimum amount of flow that must be removed from the network to disconnect the source and sink nodes.

boardmodelpaper.com 说:
Jan 10, 2024 01:39:17 PM

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.

1000 kwh battery 说:
Jul 04, 2024 03:05:25 AM

Experience obviously premium substances - you will see that person for: youibot mobile manipulator robot amr robot

godspeed clothing 说:
Mar 08, 2025 12:05:20 PM

Wonderful post. The staff is knowledgeable and first-rate. How do you view private Instagram profiles if you use the app? Using the program, I examined the most popular private Instagram profiles. Visit and read the article to find out more about the tool.

vclub 说:
Mar 08, 2025 01:15:28 PM

Therefore, learn about the rules regarding phone calls and the assistance that a reverse mobile phone lookup service may provide the next time an unexplained unknown phone number causes you or possibly both of your loved ones to be distressed.

688v 说:
May 24, 2025 07:21:18 PM

Your research shines through in this post. I admire how you've backed up your points with data and relevant examples—it adds so much credibility. It's rare to find such a balanced mix of technical depth and readability. This kind of quality content is what sets your blog apart from many others. Thank you for raising the bar and sharing knowledge that readers can genuinely learn from.

600bet 说:
May 25, 2025 03:04:39 PM

This was such a well-written and informative post! I really appreciate the depth of research and effort that went into presenting the information. The way you broke down complex ideas into simpler concepts made it so much easier to understand. I especially liked how you included practical examples and real-life applications, which made the content even more relatable. It's clear that you’re passionate about the topic, and it definitely shows in your writing. Looking forward to reading more insightful posts from you!

aa888 说:
May 25, 2025 04:58:59 PM

Thank you for such a well-written and insightful post! I’ve been struggling with staying productive while working from home, and your suggestions really hit home. I especially appreciated the emphasis on breaking tasks into smaller chunks and using the Pomodoro technique. I’ve tried it before, but never consistently – your reminder has motivated me to give it another shot. The point about minimizing distractions is so true too. I often underestimate how much time I lose checking social media. Setting dedicated “scroll times” might actually help. I also loved how you balanced practical tools with mindset changes. It’s refreshing to see both sides addressed. Thanks again for sharing your experience and tips – I’m definitely bookmarking this for future reference!

ap777. com 说:
Jun 01, 2025 10:58:51 AM

"Great read! I agree with much of what you said, especially about [insert specific idea], but I wonder how things might change if we looked at it from [insert alternative angle or question]. Have you considered the impact of I think this is a conversation worth having, and your blog is a great place to start it. Would love to hear other readers' thoughts too. Thanks again for opening up this topic!"

jun88 bet 说:
Jun 01, 2025 11:54:04 AM

"Thank you for such a well-researched and informative article. Your breakdown of was very clear, and I appreciate the balanced approach you took when presenting different sides. It's rare to find content that both educates and encourages critical thinking, and this post does just that. If you ever plan to expand on this, I’d love to see a deeper dive into Subscribed and looking forward to learning more from you!"

777vip .com 说:
Jun 01, 2025 12:57:35 PM

Reading this brought up memories of a similar incident that happened to me some time ago. I felt seen because of how similar your description was. Although they might not have the same words as you, I believe many people will be able to connect to this. It's reassuring to hear that others have experienced similar things, so thank you for sharing something so open and genuine. This kind of post fosters real connections.

ht777 说:
Jun 19, 2025 11:42:00 AM

Reading this brought back so many memories. I went through something very similar a few years ago, and I wish I had come across a post like this back then. Your advice on staying positive and focused during tough times really hit home for me. I’ve tried some of the techniques you mentioned, like journaling and meditation, and they’ve made a big difference in my life. Thanks for sharing this – it made me feel seen and supported.

567zk 说:
Jun 21, 2025 10:49:17 AM

The breadth of your research is amply displayed in this paper. It really increases your credibility, and I like how you backed up your arguments with pertinent data and examples. Such a smooth balancing act between technological depth and accessibility is uncommon. This kind of outstanding material really makes your blog stand out. I appreciate your high expectations and insightful comments.

slots 786 说:
Jun 21, 2025 01:42:38 PM

Thank you for writing such an in-depth and well-organized post. I truly appreciate the amount of research and thought you put into this. The way you broke down each section made it easy to follow, even for someone who may not be an expert on the topic. It’s clear you have a deep understanding of the subject. I especially liked the example you shared in the middle—it made the concept much more relatable. I’m definitely going to apply some of these insights to my own work. Keep up the excellent content!

noob win 说:
Jun 23, 2025 12:05:50 PM

The breadth of your research is evident in this piece. Your authority is much increased, and I appreciate how you backed up your claims with relevant examples and facts. It is rare for accessibility and technical depth to coexist so effectively. Your blog's outstanding content makes it stand out from many others. Thank you for establishing a high bar and giving people relevant information.

trapstar 说:
Jun 26, 2025 03:51:54 PM

I never thought about this topic from that angle—really opened my eyes. Appreciate the depth of research and the way you broke things down.

trapstar 说:
Jun 28, 2025 01:44:46 PM

Whoa, your writing truly has astonished me! Your content already has a wonderful tone and organization for someone who is just starting a blog. This post was well-written, insightful, and considerate. It's clear to me that you've done your homework. Keep continuing; a lot of visitors could find your site to be a useful resource. I hope your trip is filled with success!

spribe game 说:
Jul 03, 2025 11:44:32 AM

I appreciate your post being so well-written and educational. I thought it was great how you explained the subject; it made things extremely clear. I'll be reading more from you soon!

nofs tracksuit 说:
Jul 06, 2025 02:15:12 PM

Wow, this was an incredibly informative and well-structured post! I truly appreciate the amount of effort and research you’ve put into explaining this topic. As someone who's been trying to get a better grasp on this subject, your breakdown really helped connect the dots for me. I especially liked how you included real-life examples and practical tips that readers can immediately apply. Keep up the amazing work — your blog is quickly becoming one of my go-to resources for reliable information. Looking forward to more valuable content like this in the future!

a777 game 说:
Jul 17, 2025 02:12:12 PM

Your essay demonstrates excellent research and a thorough comprehension of the subject. Your credibility is much increased when you can support your arguments with concrete examples and reliable data. It's great to see such a smooth blending of technical precision and depth. This kind of content truly sets your blog apart. Thank you for establishing such a high bar and providing such useful information.

nofs jogginganzug 说:
Jul 19, 2025 03:25:34 PM

Your post about your trip was really motivating. I felt as though I was there in person thanks to the stunning pictures and detailed descriptions that took me there. I appreciated your personal advice and the thorough itinerary you provided; they are really helpful to anyone organizing a vacation of this nature. I was even more eager to travel after reading your fascinating observations on the local cuisine and culture. I appreciate you sharing your experiences so freely; it has inspired me to soon begin organizing my own trip!

x777 说:
Jul 20, 2025 12:58:01 PM

Great read! One small suggestion: maybe consider breaking the longer paragraphs into smaller chunks for easier reading. Still, the content was excellent!

pkgame7 说:
Aug 21, 2025 11:52:36 AM

This was one of the most insightful articles I’ve read on starting and scaling a business. Your breakdown of common pitfalls and how to avoid them was spot on. I especially liked the section where you talked about mindset and long-term planning—it really resonated with where I am right now in my journey. I’ve saved this post and will definitely revisit it as I grow my business. Keep sharing your expertise!

68q 说:
Aug 21, 2025 12:47:18 PM

"Your article is a great balance of informative and easy-to-read writing. I appreciate the way you’ve explained complex ideas in such a clear way. One thing I’m curious about is how your advice might change for people in different situations or industries. Either way, this was a fantastic post and I’ll definitely be keeping an eye on your future content."

aa123 love 说:
Aug 21, 2025 01:35:08 PM

"I truly enjoyed reading this from start to finish. The flow was smooth, the points were well-organized, and your voice as a writer really shines through. I hope you continue to create more posts like this, because it’s the kind of content that keeps readers coming back for more. Thank you for your time and effort in putting this together."

3336 bet 说:
Aug 21, 2025 02:23:41 PM

I appreciate you taking the time to write such an insightful and lucid essay. It's great to come across a blog post that actually offers value in a world where there is so much superficial material available online. This taught me a lot, and I like how you organized the information to make it simple to understand. I'll save this to my bookmarks so I can find it later if I need a reminder.

H555 Game 说:
Oct 20, 2025 11:26:59 AM

“This is such a well-written article. I learned a lot from it, and I’ll definitely be applying some of these tips in my own life.”

vclub 说:
Oct 21, 2025 01:48:15 PM

“This was a very detailed and informative post, thank you for putting it together. I really liked how you included practical tips instead of just general advice. Do you plan on covering this subject in even more depth in the future? I’d definitely be interested in reading more.”

Vg70 game 说:
Dec 02, 2025 11:36:37 AM

I absolutely loved reading this! You explained everything in such an engaging way that it kept me interested from start to finish. I also liked how you included real-life examples — it made the content feel much more relatable. Have you ever considered expanding this topic into a series? I think a follow-up post could be really useful for readers who want to go deeper.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter