void init()
{
	int i;

	scanf("%d%d", &N, &K);
	memset(net, 0, sizeof(net));
	num.clear();
	for (i = 0; i < N; i++)
	{
		scanf("%d%d%d", &itv[i].a, &itv[i].b, &itv[i].w);
		num.insert(itv[i].a);
		num.insert(itv[i].b);
	}
	int id = 1;
	for (set<int> ::iterator it = num.begin(); it != num.end(); ++it, ++id)
	{
		ID[*it] = id;
	}
	for (i = 0; i <= id; i++)
	{
		net[i][i+1].c = K;
		net[i][i+1].w = 0;
	}
	for (i = 0; i < N; i++)
	{
		net[ID[itv[i].a]][ID[itv[i].b]].c = 1;
		net[ID[itv[i].a]][ID[itv[i].b]].w = -itv[i].w;
		net[ID[itv[i].b]][ID[itv[i].a]].w = itv[i].w;
	}
	minc = 0;
	n = id + 2;
	s = 0;
	t = n - 1;
}

• 我基本明白你的意思了。这样就是有最多400个节点，600条边，应该说规模不算大啊。不过我觉得case数可能很多，因为我cin就TLE，scanf就WA。等我也试试看你的图再说。 (0) ImLazy 2008-09-29 15:36:52
• 我用你的构图法AC了。谢谢。 (0) ImLazy 2008-09-29 21:24:41
  • 啊，看来我的费用流写的太垃圾了，能发我下你的code么？ (0) 20053565 2008-09-29 21:38:10
    • 好的，我已经发好了。 (0) ImLazy 2008-09-30 19:41:54
• 用邻接表吧～ Yen's improvement 加速 (722) cuiaoxiang 2008-09-30 23:38:35
• Re:这是我的建图 但是我TLE了 (742) abilitytao 2010-03-30 16:11:30