Submission #596475
Source Code Expand
#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 Info
Submission Time
2015-12-19 23:16:08+0900
Task
H - Dungeon
User
kuangbin
Language
C++ (G++ 4.6.4)
Score
0
Code Size
3809 Byte
Status
WA
Exec Time
1599 ms
Memory
24424 KB
Compile Error
./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]
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 100
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt, sample_03.txt
All
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
Case Name
Status
Exec Time
Memory
colorful1_01.txt
WA
84 ms
24412 KB
colorful1_02.txt
WA
70 ms
24360 KB
colorful1_03.txt
WA
76 ms
24368 KB
colorful2_01.txt
WA
165 ms
24360 KB
colorful2_02.txt
WA
75 ms
24360 KB
colorful2_03.txt
WA
77 ms
24360 KB
colorful3_01.txt
WA
1599 ms
24416 KB
colorful3_02.txt
WA
1184 ms
24364 KB
colorful3_03.txt
WA
1389 ms
24424 KB
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
72 ms
24356 KB
interval_02.txt
WA
78 ms
24364 KB
interval_03.txt
WA
273 ms
24364 KB
interval_04.txt
WA
80 ms
24364 KB
random_01.txt
WA
78 ms
24368 KB
random_02.txt
WA
82 ms
24368 KB
random_03.txt
WA
76 ms
24368 KB
random_04.txt
WA
119 ms
24256 KB
random_05.txt
WA
85 ms
24296 KB
random_06.txt
WA
115 ms
24300 KB
random_exp_01.txt
WA
72 ms
24300 KB
random_exp_02.txt
WA
72 ms
24296 KB
random_exp_03.txt
AC
72 ms
24300 KB
random_max_01.txt
WA
80 ms
24304 KB
random_max_02.txt
WA
212 ms
24308 KB
random_max_03.txt
WA
533 ms
24236 KB
random_max_04.txt
WA
195 ms
24300 KB
random_max_05.txt
WA
202 ms
24296 KB
random_max_06.txt
WA
89 ms
24308 KB
random_max_07.txt
WA
603 ms
24304 KB
random_max_08.txt
WA
231 ms
24292 KB
random_max_09.txt
WA
83 ms
24304 KB
random_max_10.txt
WA
153 ms
24300 KB
random_select_01.txt
WA
72 ms
24304 KB
random_select_02.txt
WA
71 ms
24300 KB
random_select_03.txt
WA
69 ms
24300 KB
random_select_04.txt
WA
70 ms
24292 KB
random_select_05.txt
WA
69 ms
24300 KB
random_select_06.txt
WA
70 ms
24292 KB
random_select_07.txt
WA
70 ms
24292 KB
random_select_08.txt
WA
70 ms
24300 KB
random_select_09.txt
WA
69 ms
24300 KB
random_select_10.txt
WA
69 ms
24304 KB
random_small_01.txt
AC
68 ms
24284 KB
random_small_02.txt
WA
68 ms
24284 KB
random_small_03.txt
WA
72 ms
24280 KB
random_small_04.txt
WA
68 ms
24300 KB
random_small_05.txt
WA
70 ms
24292 KB
random_small_06.txt
WA
69 ms
24292 KB
random_small_07.txt
WA
70 ms
24300 KB
random_small_08.txt
WA
68 ms
24296 KB
random_small_09.txt
WA
69 ms
24300 KB
random_small_10.txt
WA
89 ms
24336 KB
sample_01.txt
AC
68 ms
24296 KB
sample_02.txt
AC
68 ms
24296 KB
sample_03.txt
AC
68 ms
24300 KB