The Online Judge board
https://onlinejudge.org/board/
If you want to speed up a push-preflow algorithm, the most useful optimization is a Global Relabelling heuristic. After every |V| relabels (or lift's), compute new height function: h(u) = min(d(u,t), |V|+d(u,s)). (here, d(u,v) is shortest distance between u and v, in edges). This can be done with two BFSs, from the source and the sink.
Code: Select all
/
)
Code: Select all
/*"Internet Bandwidth"*/
/*preflow-push with Global Relabelling Heuristic*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define min(a,b)((a)<(b)?(a):(b))
#define oo SHRT_MAX
#define N 101
int s,t,n;
int c[N][N],e[N],h[N],residual[N][N];
int f[N][N];
int d[N][2];
int visited[N];
int Q[N];
int last,first;
init(){
last=-1;first=0;
}
enqueue(int x,int circle,int ind){
Q[++last]=x;
d[x][ind]=circle;
visited[x]=1;
}
int dequeue(int *x,int ind){
*x=Q[first++];
return d[*x][ind];
}
int empty(){
return(last<first);
}
bfs(int root){
int u,v;
int circle;
int ind=0;
if(root==t)
ind=1;
memset(visited,0,sizeof(visited));
init();
enqueue(t,0,ind);
do{
circle=dequeue(&v,ind);
++circle;
for(u=1;u<=n;u++)
if(residual[v][u]>0 && !visited[u])
enqueue(u,circle,ind);
}while(!empty());
}
new_height()
{
int u;
for(u=1;u<=n;u++)
if(d[u][1]<oo)
h[u]=d[u][1];
else if(d[u][0]<oo)
h[u]=(n+d[u][0]);
else
h[u]=(2*n-1);
}
init_preflow()
{
int u,w;
memset(f,0,sizeof(f));
memset(e,0,sizeof(e));
memset(h,0,sizeof(h));
h[s]=n;
for(u=1;u<=n;u++)
if(w=c[s][u])
{
f[s][u]=w;
f[u][s]=-w;
residual[s][u]=c[s][u]-f[s][u];
residual[u][s]=c[u][s]-f[u][s];
e[u]=w;
}
}
relabel(int u)
{
int v;
int m=oo;
for(v=1;v<=n;v++)
if(m>h[v] && residual[u][v]>0)
m=h[v];
h[u]=(m+1);
}
push(int u,int v)
{
int d=min(e[u],residual[u][v]);
f[u][v]+=d;
residual[u][v]=(c[u][v]-f[u][v]);
f[v][u]=-f[u][v];
residual[v][u]=(c[v][u]-f[v][u]);
e[u]-=d;
e[v]+=d;
}
int get_overflowing()
{
int u;
for(u=1;u<=n;u++)
if(e[u] && u!=t && u!=s)
return u;
return 0;
}
generic_preflow_push()
{
int u,v;
int relabel_counter=0;
init_preflow();
while(u=get_overflowing())
{
for(v=1;v<=n;v++)
if(h[u]==h[v]+1 && residual[u][v]>0)
{
push(u,v);
goto next;
}
relabel(u);
++relabel_counter;
if(relabel_counter==n)
{
memset(d,oo,sizeof(d));
bfs(s);
bfs(t);
new_height();
relabel_counter=0;
}
next:continue;
}
}
int main()
{
int i,j,k,volume,cs=0;
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
scanf("%d\n",&n);
while(n)
{
scanf("%d %d %d\n",&s,&t,&k);
while(k--)
{
scanf("%d %d %d\n",&i,&j,&volume);
c[i][j]+=volume;
c[j][i]=c[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
residual[i][j]=c[i][j];
generic_preflow_push();
printf("Network %d\nThe bandwidth is %d.\n\n",++cs,e[t]);
scanf("%d\n",&n);
if(n)
memset(c,0,sizeof(c));
else
return 0;
}
return 0;
}Please read documentation on memset(); memset() works with bytes, not int's.memset(d,oo,sizeof(d));
It's MSU's new policy.got something from mexmat MGU (Maxim Babenko), but "page cannot be opened".
Code: Select all
#include<stdio.h>
#include<queue>
using namespace std;
int cap[1025][1025],flow[1025][1025],n,m,s,t,cp[25][1025];
int total[25];
void init()
{
int i,j;
for(i=0;i<=n;i++) total[i]=0;
for(i=0;i<t;i++){
for(j=0;j<t;j++){
cap[i][j]=flow[i][j]=0;
}
}
for(i=n+1;i<t;i++) {cap[i][t]=1;flow[i][t]=0;}
}
int max_flow()
{
int i,p[1025],now,before;
bool visited[1025];
queue<int> Q;
for(i=0;i<=t;i++){
visited[i]=false;
p[i]=-1;
}
Q.push(s);
p[s]=-1;
visited[s]=true;
while(!Q.empty()){
now=Q.front();
Q.pop();
for(i=1;i<=t;i++){
if((cap[now][i]-flow[now][i])>0 && visited[i]==false){
Q.push(i);
visited[i]=true;
p[i]=now;
}
}
if(visited[t]==true) break;
}
if(visited[t]==false) return 0;
now=t;
while(p[now]!=-1){
before=p[now];
if(now>n && now<t && before>=1 && before<=n) {
cp[before][total[before]++]=now;
}
flow[before][now]++;
flow[now][before]--;
now=before;
}
return 1;
}
int main()
{
int i,j,k,cn,capacity,count;
while(true){
scanf("%d %d",&n,&m);
if(!n && !m) break;
s=capacity=0;
t=n+m+1;
init();
for(i=1;i<=n;i++) {
scanf("%d",&cap[s][i]);
capacity+=cap[s][i];
}
for(i=n+1;i<t;i++){
scanf("%d",&k);
for(j=0;j<k;j++){
scanf("%d",&cn);
cap[cn][i]=1;
}
}
count=0;
while(max_flow() ) count++;
if(count<capacity) printf("0\n");
else {
printf("1\n");
for(i=1;i<=n;i++){
for(j=0;j<total[i];j++) {
if(j) printf(" ");
printf("%d",cp[i][j]-n);
}
printf("\n");
}
}
}
return 0;
}Code: Select all
solution changed ....
Code: Select all
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define SIZE 1010
using namespace std;
//globals
int cap[25];
int filled[25];
bool adj[25][SIZE];
int NK,NP;
bool seen[SIZE];
int leftM[25][150];
int rightM[SIZE];
bool bpm(int u)
{
int j;
bool flag=true;
while(filled[u]<cap[u] && flag)
{
flag=false;
for(j=1;j<=NP;j++)if(adj[u][j])
{
if(seen[j])continue;
else seen[j]=true;
if(rightM[j]<0)
{
rightM[j]=u;
filled[u]++;
leftM[u][filled[u]]=j;
flag=true;
break;
}
int x=rightM[j];
filled[x]--;
if(bpm(x))
{
rightM[j]=u;
filled[u]++;
leftM[u][filled[u]]=j;
flag=true;
break;
}
else
{
filled[x]++;
}
}
}
if(filled[u]==cap[u])
return true;
return false;
}
int main(void)
{
int i,j,n,p;
while(true)
{
scanf("%d%d",&NK,&NP);
if(NP==0 && NK==0)
break;
//input
for(i=1;i<=NK;i++)
scanf("%d",&cap[i]);
memset(adj,0,sizeof(adj));
for(i=1;i<=NP;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
{
scanf("%d",&p);
adj[p][i]=true;
}
}
memset(filled,0,sizeof(filled));
memset(leftM,-1,sizeof(leftM));
memset(rightM,-1,sizeof(rightM));
bool flag =true;
for(i=1;i<=NK && flag;i++)
{
memset(seen,false,sizeof(seen));
if(!bpm(i))
flag=false;
}
if(!flag)
printf("0\n");
else
{
printf("1\n");
for(i=1;i<=NK;i++)
{
bool start=true;
for(j=1;j<=cap[i];j++)
{
if(start)
start=!start;
else
printf(" ");
printf("%d",leftM[i][j]);
}
printf("\n");
}
}
}
return 0;
}
No.Kallol wrote:here I tried it with DFS ...but still WA
......
counter case plzzzzzzzzz......
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100 /* maximum number of vertices */
#define MAXDEGREE 50 /* maximum outdegree of a vertex */
#define QUEUESIZE 1000
#define X 0 /* x-coordinate index */
#define Y 1 /* y-coordinate index */
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef struct {
int q[QUEUESIZE+1]; /* body of queue */
int first; /* position of first element */
int last; /* position of last element */
int count; /* number of queue elements */
} queue;
typedef struct {
int edges[MAXV+1][MAXDEGREE]; /* adjacency info */
int degree[MAXV+1]; /* outdegree of each vertex */
int nvertices; /* number of vertices in the graph */
int nedges; /* number of edges in the graph */
} graph;
typedef struct {
int v; /* neighboring vertex */
int capacity; /* capacity of edge */
int flow; /* flow through edge */
int residual; /* residual capacity of edge */
} edge;
typedef struct {
edge edges[MAXV][MAXDEGREE]; /* adjacency info */
int degree[MAXV]; /* outdegree of each vertex */
int nvertices; /* number of vertices in the graph */
int nedges; /* number of edges in the graph */
} flow_graph;
int min (int a,int b){
if (a > b)
return b;
else
return a;
}
int init_queue(queue *q)
{
q->first = 0;
q->last = QUEUESIZE-1;
q->count = 0;
}
int enqueue(queue *q, int x)
{
if (q->count >= QUEUESIZE)
printf("Warning: queue overflow enqueue x=%d\n",x);
else {
q->last = (q->last+1) % QUEUESIZE;
q->q[ q->last ] = x;
q->count = q->count + 1;
}
}
int dequeue(queue *q)
{
int x;
if (q->count <= 0) printf("Warning: empty queue dequeue.\n");
else {
x = q->q[ q->first ];
q->first = (q->first+1) % QUEUESIZE;
q->count = q->count - 1;
}
return(x);
}
int empty(queue *q)
{
if (q->count <= 0) return (TRUE);
else return (FALSE);
}
int initialize_graph(flow_graph *g)
{
int i; /* counter */
g -> nvertices = 0;
g -> nedges = 0;
for (i=0; i<MAXV; i++) g->degree[i] = 0;
}
int insert_flow_edge(flow_graph *g, int x, int y,bool directed, int w)
{
if (g->degree[x] > MAXDEGREE)
printf("Warning: insertion(%d,%d) exceeds degree bound\n",x,y);
g->edges[x][g->degree[x]].v = y;
g->edges[x][g->degree[x]].capacity = w;
g->edges[x][g->degree[x]].flow = 0;
g->edges[x][g->degree[x]].residual = w;
g->degree[x] ++;
if (directed == FALSE)
insert_flow_edge(g,y,x,TRUE,w);
else
g->nedges ++;
}
int read_flow_graph(flow_graph *g,int directed,int c,int p)
{
int i,n; /* counter */
int m; /* number of edges */
int x,y,w; /* placeholder for edge and weight */
int count=0;
int sink;
sink=c+p+2;
initialize_graph(g);
for (i=1;i<=c;i++){
scanf("%d",&w);
insert_flow_edge(g,1,i+1,directed,w);
count++;
}
for (i=1; i<=p; i++) {
scanf("%d",&m);
if (m<=c&&m>0)
for(n=0;n<m;n++){
scanf("%d",&x);
if (x<=c&&x>0)
insert_flow_edge(g,x+1,c+i+1,directed,1);
}
insert_flow_edge(g,c+i+1,sink,directed,1);
}
g->nvertices=sink;
}
edge *find_edge(flow_graph *g, int x, int y)
{
int i; /* counter */
for (i=0; i<g->degree[x]; i++)
if (g->edges[x][i].v == y)
return( &g->edges[x][i] );
return(NULL);
}
int add_residual_edges(flow_graph *g)
{
int i,j; /* counters */
for (i=1; i<=g->nvertices; i++)
for (j=0; j<g->degree[i]; j++)
if (find_edge(g,g->edges[i][j].v,i) == NULL)
insert_flow_edge(g,g->edges[i][j].v,i,TRUE,0);
}
int print_flow_graph(flow_graph *g)
{
int i,j; /* counters */
for (i=1; i<=g->nvertices; i++) {
printf("%d: ",i);
for (j=0; j<g->degree[i]; j++)
printf(" %d(%d,%d,%d)",g->edges[i][j].v,
g->edges[i][j].capacity,
g->edges[i][j].flow,
g->edges[i][j].residual);
printf("\n");
}
}
bool processed[MAXV]; /* which vertices have been processed */
bool discovered[MAXV]; /* which vertices have been found */
int parent[MAXV]; /* discovery relation */
bool finished = FALSE; /* if true, cut off search immediately */
int initialize_search(flow_graph *g)
{
int i; /* counter */
for (i=1; i<=g->nvertices; i++) {
processed[i] = FALSE;
discovered[i] = FALSE;
parent[i] = -1;
}
}
int bfs(flow_graph *g, int start)
{
queue q; /* queue of vertices to visit */
int v; /* current vertex */
int i; /* counter */
init_queue(&q);
enqueue(&q,start);
discovered[start] = TRUE;
while (empty(&q) == FALSE) {
v = dequeue(&q);
for (i=0; i<g->degree[v]; i++)
if (valid_edge(g->edges[v][i]) == TRUE) {
if (discovered[g->edges[v][i].v] == FALSE) {
enqueue(&q,g->edges[v][i].v);
discovered[g->edges[v][i].v] = TRUE;
parent[g->edges[v][i].v] = v;
}
}
}
}
bool valid_edge(edge e)
{
if (e.residual > 0) return (TRUE);
else return(FALSE);
}
int find_path(int start,int end,int parents[])
{
if ((start == end) || (end == -1))
printf("\n%d",start);
else {
find_path(start,parents[end],parents);
printf(" %d",end);
}
}
int path_volume(flow_graph *g, int start, int end, int parents[])
{
edge *e; /* edge in question */
edge *find_edge();
if (parents[end] == -1) return(0);
e = find_edge(g,parents[end],end);
if (start == parents[end])
return(e->residual);
else
return( min(path_volume(g,start,parents[end],parents), e->residual) );
}
int augment_path(flow_graph *g, int start, int end, int parents[], int volume)
{
edge *e; /* edge in question */
edge *find_edge();
if (start == end) return;
e = find_edge(g,parents[end],end);
e->flow += volume;
e->residual -= volume;
e = find_edge(g,end,parents[end]);
e->residual += volume;
augment_path(g,start,parents[end],parents,volume);
}
int netflow(flow_graph *g, int source, int sink)
{
int volume; /* weight of the augmenting path */
add_residual_edges(g);
initialize_search(g);
bfs(g,source);
volume = path_volume(g, source, sink, parent);
while (volume > 0) {
augment_path(g,source,sink,parent,volume);
initialize_search(g);
bfs(g,source);
volume = path_volume(g, source, sink, parent);
}
}
int main(void)
{
flow_graph g; /* graph to analyze */
int source, sink; /* source and sink vertices */
int flow; /* total flow */
int i,j,tmp; /* counter */
int c,p;
scanf("%d%d",&c,&p);
while (c != 0 && p != 0){
read_flow_graph(&g,TRUE,c,p);
source=1;
sink=2+c+p;
netflow(&g,source,sink);
flow = 0;
for (j=0; j<g.degree[i+1]; j++){
if(g.edges[1][j].residual != 0){
flow=1;
}
}
if(flow == 0){
printf("1\n");
for (i=1;i<=c;i++){
for (j=0; j<g.degree[i+1]; j++){
if(g.edges[i+1][j].residual == 0){
tmp=g.edges[i+1][j].v;
tmp = tmp -c -1;
printf("%d ",tmp);
}
}
printf("\n");
}
}
else
printf("0\n");
scanf("%d%d",&c,&p);
}
//print_flow_graph(&g);
system("pause");
}Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct{
int id, quant;
}prob_cat;
typedef struct{
int id;
vector <int> cats;
}problem;
bool compare(prob_cat p1, prob_cat p2){
if (p1.quant<=p2.quant)
return true;
return false;
}
bool compare2(problem p1, problem p2){
if (p1.cats.size()<=p2.cats.size())
return true;
return false;
}
int main(){
int nk, np, i, j;
while(true){
cin>>nk>>np;
if(!nk && !np)
break;
vector< int > categories(nk);
vector< problem > problems(np);
vector< prob_cat > probs_cat(nk);
for(i=0; i<nk; i++){
probs_cat[i].id=i+1;
probs_cat[i].quant=0;
cin>>categories[i];
}
int n, cat;
for(i=0; i<np; i++){
cin>>n;
problems[i].id=i+1;
for(j=0; j<n; j++){
cin>>cat;
problems[i].cats.push_back(cat);
probs_cat[cat-1].quant++;
}
}
sort(probs_cat.begin(),probs_cat.end(),compare);
sort(problems.begin(),problems.end(),compare2);
/*for (i=0; i<np; i++){
cout<<problems[i].id<<" -- ";
for(j=0; j<problems[i].cats.size(); j++)
cout<<problems[i].cats[j]<<" ";
cout<<endl;
}*/
vector< vector <int> > result(nk,vector<int>());
int counter;
bool impossible=false;
for(i=0; i<nk; i++){
counter=0;
for(j=0; j<np; j++){
if(counter==categories[probs_cat[i].id-1])
break;
if(problems[j].id!=0){
if(find(problems[j].cats.begin(),problems[j].cats.end(),probs_cat[i].id)!=problems[j].cats.end()){
result[probs_cat[i].id-1].push_back(problems[j].id);
counter++;
problems[j].id=0;
}
}
}
if(counter!=categories[probs_cat[i].id-1]){
cout<<"0"<<endl;
impossible=true;
break;
}
}
if(!impossible){
cout<<"1"<<endl;
for(i=0; i<nk; i++){
for(j=0; j<result[i].size(); j++){
if(j>0)
cout<<" ";
cout<<result[i][j];
}
cout<<endl;
}
}
}
return 0;
}