#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;
void bellman()
{
for(int i=source;i<=sink;i++)id_of_edge_to_parent[i]=-1,dist[i]=inf;
dist[source]=0;
while(1)
{
bool change=0;
for(auto k:edges)
if(k.flow&&dist[k.from]+k.cost<dist[k.to])
{
change=1;
dist[k.to]=dist[k.from]+k.cost;
id_of_edge_to_parent[k.to]=k.id_back^1;
}
if(change==0)return;
}
}
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)
{
bellman();
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:120: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:98: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:108: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 |
7 ms |
504 KB |
Output is correct |
| 2 |
Correct |
7 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 |
8 ms |
632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
1936 KB |
Output is correct |
| 2 |
Correct |
58 ms |
1936 KB |
Output is correct |
| 3 |
Correct |
7 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
700 ms |
7132 KB |
Output is correct |
| 2 |
Correct |
685 ms |
7132 KB |
Output is correct |
| 3 |
Correct |
10 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
530 ms |
7012 KB |
Output is correct |
| 2 |
Execution timed out |
1086 ms |
12268 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
900 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
714 ms |
6692 KB |
Output is correct |
| 3 |
Correct |
15 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
1932 KB |
Output is correct |
| 2 |
Correct |
27 ms |
7012 KB |
Output is correct |
| 3 |
Execution timed out |
1092 ms |
24912 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
118 ms |
65536 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 |
274 ms |
2060 KB |
Output is correct |
| 2 |
Execution timed out |
1092 ms |
14296 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
