#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42,inf=2e9+42;
int n,m,r,t,k;
struct edge
{
int from,to,flow,cost,id_back;
};
vector<edge> edges;
vector<int> adj[nmax];
void add(int from,int to,int flow,int cost)
{
int id_back=edges.size()^1;
edge current;
current.from=from;
current.to=to;
current.flow=flow;
current.cost=cost;
current.id_back=id_back;
adj[from].push_back(edges.size());
edges.push_back(current);
}
void add_edge(int from,int to,int flow,int cost)
{
add(from,to,flow,cost);
add(to,from,0,-cost);
}
int id_of_edge_to_parent[nmax],dist[nmax];
int source,sink;
int type[nmax];//0-> solved, 1-> solving, 2-> to be discovered
deque<int> active;
void spfa()
{
for(int i=source;i<=sink;i++)id_of_edge_to_parent[i]=-1,dist[i]=inf,type[i]=2;
dist[source]=0;
type[source]=1;
active.push_back(source);
while(active.size())
{
int current=active.front();
active.pop_front();
type[current]=0;
for(auto k:adj[current])
{
//cout<<edges[k].from<<" "<<edges[k].cost<<" "<<edges[k].to<<endl;
if(edges[k].flow&&dist[edges[k].from]+edges[k].cost<dist[edges[k].to])
{
dist[edges[k].to]=dist[edges[k].from]+edges[k].cost;
id_of_edge_to_parent[edges[k].to]=edges[k].id_back^1;
if(type[edges[k].to]==2)active.push_back(edges[k].to);
else if(type[edges[k].to]==0)active.push_back(edges[k].to);
type[edges[k].to]=1;
}
}
}
//for(int i=source;i<=sink;i++)cout<<i<<" -> "<<id_of_edge_to_parent[i]<<" "<<dist[i]<<" "<<type[i]<<endl;
}
void push(int id)
{
edges[id].flow--;
edges[edges[id].id_back].flow++;
}
void min_cost_max_flow()
{
long long flow=0,cost=0;
while(1)
{
spfa();
if(dist[sink]==inf)break;
flow++;
cost=cost+dist[sink];
int node=sink;
//cout<<"path: ";
while(node!=source)
{
push(id_of_edge_to_parent[node]);
node=edges[id_of_edge_to_parent[node]].from;
//cout<<node<<" ";
}
//cout<<endl;
}
printf("%lld %lld\n",flow,cost);
for(int i=1;i<=n;i++)
{
int t_now=0;
for(auto k:adj[i])
if(n+1<=edges[k].to&&edges[k].to<=n+m&&edges[k].flow==0)
{
printf("%i %i %i\n",i,edges[k].to-n,t_now);
t_now+=r;
}
}
}
int main()
{
scanf("%i%i%i%i%i",&n,&m,&r,&t,&k);
source=0;
sink=n+m+1;
int u,v;
vector< pair<int,int> > mem={};
for(int i=1;i<=k;i++)
{
scanf("%i%i",&u,&v);
v=v+n;
mem.push_back({u,v});
}
for(int i=n+1;i<=n+m;i++)
add_edge(i,sink,1,0);
for(auto k:mem)
add_edge(k.first,k.second,1,0);
for(int i=1;i<=n;i++)
for(int j=0;(j+1)*r<=t&&j<adj[i].size();j++)
add_edge(source,i,1,(j+1)*r);
min_cost_max_flow();
return 0;
}
Compilation message
pro.cpp: In function 'int main()':
pro.cpp:137:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;(j+1)*r<=t&&j<adj[i].size();j++)
~^~~~~~~~~~~~~~
pro.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i%i%i",&n,&m,&r,&t,&k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pro.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i",&u,&v);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1936 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1936 KB |
Output is correct |
| 3 |
Correct |
6 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
7140 KB |
Output is correct |
| 2 |
Correct |
351 ms |
7292 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
7004 KB |
Output is correct |
| 2 |
Execution timed out |
1037 ms |
12336 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
468 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
332 ms |
6696 KB |
Output is correct |
| 3 |
Correct |
11 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
2060 KB |
Output is correct |
| 2 |
Correct |
27 ms |
7012 KB |
Output is correct |
| 3 |
Execution timed out |
1096 ms |
24912 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
2060 KB |
Output is correct |
| 2 |
Execution timed out |
1097 ms |
14168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
