code festival 2014 上海

Submission #596475

Source codeソースコード

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 2010;
const int MAXM = 1000010;
const long long INF = 1000000000000000000LL;
struct Edge
{
    int to,next,cap,flow;
	long long cost;
	Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,long long _cost = 0):
		to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}
}edge[MAXM];

struct ZKW_MinCostMaxFlow
{
	int head[MAXN],tot;
	int cur[MAXN];
	long long dis[MAXN];
	bool vis[MAXN];
	int ss,tt,N;//源点、汇点和点的总个数(编号是0~N-1),不需要额外赋值,调用会直接赋值
	long long min_cost;
   	int 	max_flow;
	void init()
	{
		tot = 0;
		memset(head,-1,sizeof(head));
	}
	void addedge(int u,int v,int cap,long long cost)
	{
		edge[tot] = Edge(v,head[u],cap,0,cost);
		head[u] = tot++;
		edge[tot] = Edge(u,head[v],0,0,-cost);
		head[v] = tot++;
	}
	int aug(int u,int flow)
	{
		if(u == tt)return flow;
		vis[u] = true;
		for(int i = cur[u];i != -1;i = edge[i].next)
		{
			int v = edge[i].to;
			if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] == dis[v] + edge[i].cost)
			{
				int tmp = aug(v,min(flow,edge[i].cap-edge[i].flow));
				edge[i].flow += tmp;
				edge[i^1].flow -= tmp;
				cur[u] = i;
				if(tmp)return tmp;
			}
		}
		return 0;
	}
	bool modify_label()
	{
		long long d = INF;
		for(int u = 0;u < N;u++)
			if(vis[u])
				for(int i = head[u];i != -1;i = edge[i].next)
				{
					int v = edge[i].to;
					if(edge[i].cap>edge[i].flow && !vis[v])
						d = min(d,dis[v]+edge[i].cost-dis[u]);
				}
		if(d == INF)return false;
		for(int i = 0;i < N;i++)
			if(vis[i])
			{
				vis[i] = false;
				dis[i] += d;

			}
		return true;
	}
	/*
	 * 直接调用获取最小费用和最大流
	 * 输入: start-源点,end-汇点,n-点的总个数(编号从0开始)
	 * 返回值: pair<int,int> 第一个是最小费用,第二个是最大流
	 */
	pair<long long,int> mincostmaxflow(int start,int end,int n)
	{
		ss = start, tt = end, N = n;
		min_cost = 0;
	   	max_flow = 0;
		for(int i = 0;i < n;i++)dis[i] = 0;
		while(1)
		{
			for(int i = 0;i < n;i++)cur[i] = head[i];
			while(1)
			{
				for(int i = 0;i < n;i++)vis[i] = false;
				int tmp = aug(ss,1000000000);
				if(tmp == 0)break;
				max_flow += tmp;
				min_cost += tmp*dis[ss];
			}
			if(!modify_label())break;
		}
		return make_pair(min_cost,max_flow);
	}
}solve;

pair<int,int>p[1000];
pair<int,int>da[1000];
pair<int,int>de[1000];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
	while(scanf("%d",&n) == 1) {
		for(int i = 0;i < n;i++) {
			scanf("%d%d", &p[i].first, &p[i].second);
		}
		long long sum = 0;
		int num1 = 0;
		int num2 = 0;
		int cnt = 0;
		for (int i = n-1;i >= 0;i--) {
			if (p[i].first == 2) {
				sum += p[i].second;
				cnt++;
			} else if (p[i].first == 0) {
				da[num1++] = make_pair(cnt, p[i].second);
			} else {
				de[num2++] = make_pair(cnt, p[i].second);
			}
		}
		solve.init();
		for (int i = 1;i <= num1;i++)solve.addedge(0,i,1,0);
		for (int i = num1+1;i <= num1+num2;i++)solve.addedge(i,num1+num2+1,1,0);
		for (int i = 0;i < num1;i++)
			for(int j = 0;j < num2;j++) {
				long long cost = (long long)min(da[i].first, de[j].first)*de[j].second - da[i].second;
				if (cost < 0)cost = 0;
				solve.addedge(i+1, num1+1+j, 1, -cost);
			}
		pair<long long,int>tmp = solve.mincostmaxflow(0,num1+num2+1,num1+num2+2);
		long long ans = sum + tmp.first;
		printf("%lld\n",ans);
	}
    return 0;
}

Submission

Task問題 H - Dungeon
User nameユーザ名 102_kuangbin
Created time投稿日時
Language言語 C++ (G++ 4.6.4)
Status状態 WA
Score得点 0
Source lengthソースコード長 3809 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:125:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 0 / 100 colorful1_01.txt,colorful1_02.txt,colorful1_03.txt,colorful2_01.txt,colorful2_02.txt,colorful2_03.txt,colorful3_01.txt,colorful3_02.txt,colorful3_03.txt,corner_01.txt,corner_02.txt,corner_03.txt,corner_04.txt,corner_05.txt,corner_06.txt,interval_01.txt,interval_02.txt,interval_03.txt,interval_04.txt,random_01.txt,random_02.txt,random_03.txt,random_04.txt,random_05.txt,random_06.txt,random_exp_01.txt,random_exp_02.txt,random_exp_03.txt,random_max_01.txt,random_max_02.txt,random_max_03.txt,random_max_04.txt,random_max_05.txt,random_max_06.txt,random_max_07.txt,random_max_08.txt,random_max_09.txt,random_max_10.txt,random_select_01.txt,random_select_02.txt,random_select_03.txt,random_select_04.txt,random_select_05.txt,random_select_06.txt,random_select_07.txt,random_select_08.txt,random_select_09.txt,random_select_10.txt,random_small_01.txt,random_small_02.txt,random_small_03.txt,random_small_04.txt,random_small_05.txt,random_small_06.txt,random_small_07.txt,random_small_08.txt,random_small_09.txt,random_small_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
colorful1_01.txt WA
colorful1_02.txt WA
colorful1_03.txt WA
colorful2_01.txt WA
colorful2_02.txt WA
colorful2_03.txt WA
colorful3_01.txt WA
colorful3_02.txt WA
colorful3_03.txt WA
corner_01.txt AC 74 ms 24364 KB
corner_02.txt AC 73 ms 24364 KB
corner_03.txt AC 76 ms 24360 KB
corner_04.txt AC 73 ms 24360 KB
corner_05.txt AC 70 ms 24364 KB
corner_06.txt AC 70 ms 24364 KB
interval_01.txt WA
interval_02.txt WA
interval_03.txt WA
interval_04.txt WA
random_01.txt WA
random_02.txt WA
random_03.txt WA
random_04.txt WA
random_05.txt WA
random_06.txt WA
random_exp_01.txt WA
random_exp_02.txt WA
random_exp_03.txt AC 72 ms 24300 KB
random_max_01.txt WA
random_max_02.txt WA
random_max_03.txt WA
random_max_04.txt WA
random_max_05.txt WA
random_max_06.txt WA
random_max_07.txt WA
random_max_08.txt WA
random_max_09.txt WA
random_max_10.txt WA
random_select_01.txt WA
random_select_02.txt WA
random_select_03.txt WA
random_select_04.txt WA
random_select_05.txt WA
random_select_06.txt WA
random_select_07.txt WA
random_select_08.txt WA
random_select_09.txt WA
random_select_10.txt WA
random_small_01.txt AC 68 ms 24284 KB
random_small_02.txt WA
random_small_03.txt WA
random_small_04.txt WA
random_small_05.txt WA
random_small_06.txt WA
random_small_07.txt WA
random_small_08.txt WA
random_small_09.txt WA
random_small_10.txt WA
sample_01.txt AC 68 ms 24296 KB
sample_02.txt AC 68 ms 24296 KB
sample_03.txt AC 68 ms 24300 KB