10511 - Councilling

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10511 - Councilling

I don't know how to solve it at all Could someone give me a hint?
thx

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The problem is bipartite matching with some extra constraints. I solved it the common way to solve bipartite matching, i.e. I build a network (but have to add some pieces to incorporate the constraints in the network) and find a maximum flow.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
I thought it as a network flow problem before
But I don't know how to build a graph.
FIrst,I create every edge with cap 1 from name to it's club
Second, I create a source node,add edge from source to name
Third, I create a sink node, add edge from club to sink
But there may be conflict that the limit of people of the party windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
I have thought the method to solve it.
Thx lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

How to build the network?

Hi,

I was thinking about this problem but could not find a way to build the network with the problem constraints to find the matching.

Could someone give me a hint in how to do this??
[]'s

Lucindo

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
hi all,

this problem seems to me very difficult. i manage to create a network. but main problem is i got TLE.
there may be 1000 member and the number of clubs and number of party is not menteion in the problem . so i have to take a larege number of node. so how can i manage to solve this problem with in the time limit.
i use Ford Fulkerson algorithm.

thanks
__nOi.m....

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Hi! I just solved this problem using Edmonds-Karp maximum flow algorithm, where the time complexity is O(VE^2). It runs in 0.7 sec, so I think it's your implementation that is wrong but not your algorithm.

And, you can use some preflow-push (V^2E) or lift-to-front(V^3), but in this problem E is likely to be linear to V, so it won't have that *much* difference. ps) Just in case, did you use the matrix representation for your network? That will cause a lot of overhead that is not needed.
JongMan @ Yonsei

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Thanks for Help.
I got Accepted at last. __nOi.m....

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Help needed

Hi, I'm trying to solve this problem, but always got wrong answer.

I build a graph and run maximum flow.
If maxflow==number of club, then we can build
the solution, otherwise it's impossible.

The graph is as this:

souce--->every party, content ==(number of club -1)/2;
every man's party---->man, content==1;
every man ----> each of his club, content==1;
every club--->sink, content==1;

I think my method is correct.
Can anyone give some hints?

coconut
New poster
Posts: 7
Joined: Thu May 27, 2004 7:23 pm
Location: Honolulu
Yup...I got W.A. as well,

Basically I store the flow in the forward-star fashion...should be very fast indeed.

Is there anyone has a tricky test case?

Thanks,

coconut
New poster
Posts: 7
Joined: Thu May 27, 2004 7:23 pm
Location: Honolulu
Can anyone advise what should be the output, in case that the number of clubs is 0?

something like that

Code: Select all

1

john yatch
I think than should output "Impossible" isnt it?

thanks!

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:

Code: Select all

1

john yatch
For this testdata , my Accepted program output nothing .. not "Impossible."

And my method is the same as hujialie's , it's the correct algorithm for this problem. Maybe he made some mistake on programming.

chenta
New poster
Posts: 1
Joined: Thu Jul 11, 2002 11:19 am

10511 Councilling -- Algorithm problem

Hi, I try to use the maxflow algorithm to slove this problem.

I transform the problem to the graph like this:

source -> every club , capacity=1
club -> all of the member, capacity=1
member -> party, capacity=1
party -> sink, capacity = (club number is even)?(club number)/2-1:(club number)/2

I alreday read the previous aritcal about this problem, the algorithm they used is just inverse every edge in my graph, did it make any difference?

Could someone give me a hint?

Thanks.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10511 - Councilling

Hi all,
i implemented a maxFlow algorithm using adjecency list ...but getting Lime limit ... could some one help me how to avoid this problem ...
thanks in advance ...

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
struct Edge{
int src,des,flow,cap;
Edge(int s,int d,int f,int c):src(s),des(d),flow(f),cap(c){};
void print(){ printf("(%d %d %d) ",des,flow,cap); }
};
vector<Edge> Graph;
string in;
int type;
const int src=0,sink=1;
int net(int u,int v){
FOR(i,Graph[u].size() )
if(Graph[u][i].des==v)
return Graph[u][i].cap;
}
int q,qf,qe,parent,mark;
int CA=0;
int flow(int u,int v){
FOR(i,Graph[u].size() )
if(Graph[u][i].des==v)
return Graph[u][i].flow;
}
void setflow(int u,int v,int val){
FOR(i,Graph[u].size() )
if(Graph[u][i].des==v)
{Graph[u][i].flow=val ;break;}
}
int Ford_Folkerson(int src,int sink){
int maxflow=0;
while(true){
++CA;
qf=qe=0;
q[qe++]=src;
mark[src]=CA;
parent[src]=-1;
bool found=false;
while(qf<qe){
int u=q[qf++];
if(u==sink){found=true;break;}
for(int i=0;i<Graph[u].size();++i){
int v=Graph[u][i].des;
if(mark[v]!=CA && Graph[u][i].cap-Graph[u][i].flow >0)
parent[v]=u,mark[v]=CA,q[qe++]=v;
}
}
if(found==false)break;
int bot = 0x7FFFFFFF;
for(int u=sink,v=parent[u];v!=-1;u=v,v=parent[u] )
bot = min(bot,net(v,u)-flow(v,u) );
for(int u=sink,v=parent[u];v!=-1;u=v,v=parent[u] )
setflow(v,u,flow(v,u)+bot ),setflow(u,v,-flow(v,u));
maxflow+=bot;
}
return maxflow;
}
int main(){
int cas;
//freopen("in.txt","r",stdin);
scanf("%d",&cas);
char line,str;
gets(line);
gets(line);
for(int ca=0;ca<cas;++ca){
if(ca)putchar('\n');
memset(type,0,sizeof(type) );
int peopleC=0,partyC=0,clubC=0,src=0,sink=1,vertexC=2;
map<string ,int> m;
while( gets(line) && line ){
int pos=0,t;
//printf(">%s\n",line);
sscanf(line+pos,"%s%n",str,&t);	pos+=t;
//puts(str);
int r=m[str]=vertexC++;
in[r]=str;
type[r]=1;//resident..
peopleC++;
sscanf(line+pos,"%s%n",str,&t);	pos+=t;
//puts(str);
int p= m.find(str)==m.end()? partyC++,m[str]=vertexC++:m[str];
type[p]=2; // party ;
Graph[r].push_back( Edge(r,p,0,0) );
Graph[p].push_back( Edge(p,r,0,1) );
while(sscanf(line+pos,"%s%n",str,&t) >0 ){pos+=t;
int c = m.find(str)==m.end()? clubC++,m[str]=vertexC++:m[str];
type[c]=3; //club
in[c]=str;
Graph[c].push_back( Edge(c,r,0,0) );
Graph[r].push_back( Edge(r,c,0,1) );
}
}
int cap= (clubC-1)/2;
FOR(i,vertexC){
if(type[i]==2){
Graph[i].push_back(Edge(i,sink,0,0) );
Graph[sink].push_back(Edge(sink,i,0,cap) );
}
if(type[i]==3){
Graph[src].push_back(Edge(src,i,0,0) );
Graph[i].push_back(Edge(i,src,0,1) );
}
}
if(Ford_Folkerson(sink,src)==clubC){
//printf("Possisbsle\n");
FOR(i,vertexC){
if(type[i]==1){
FOR(k,Graph[i].size()){
if(Graph[i][k].flow==1 /*&& type[ Graph[i][k].des ]==2*/)
printf("%s %s\n",in[i].c_str(),in[Graph[i][k].des].c_str());
}
}
}
}
else printf("impossible\n");
FOR(i,vertexC)Graph[i].clear();

}
return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Contact:

Re: 10511 - Councilling

I implemented a max flow.

SuperSource to all club, cap = 1.
From all club to each of its member, cap = 1;
From all member to their party, cap = 1;
From each party to another extra node, cap = ( no. of club + 1 ) / 2 - 1;
From each extra node to supersink, cap = inf.

Code: Select all

/***********Template Starts Here***********/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define all(c) (c).begin(),(c).end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())

typedef long long vlong;
typedef unsigned long long uvlong;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;
const vlong maxint = 2147483647;
const vlong minint = -2147483648;

using namespace std;

/***********Template Ends Here***********/

char buf;
char b1, b2;

map < int, string > m2;

vector < int > club, pol;
int node;

map < string, int > m;

int gf;

vector < int > v;
void build ()
{
memset ( gf, 0, sizeof gf );
int i;
for ( i = 1; i <= node; i++ ) v[i].clear();

int j;
for ( i = 1; i <= node; i++ )
{
for ( j = 1; j <= node; j++ )
{
if ( adj[i][j] != 0 )
{
v[i].pb ( j );
v[j].pb ( i );
}
}
}
}

int vis;
int pre;

void inc_flow ( int n, int cost )
{
if ( n == 1 )
{
return;
}

int par = pre[n];
inc_flow( par, cost );

gf[par][n] -= cost;
gf[n][par] += cost;

}

int path()
{
memset ( vis, 0, sizeof vis );
vis = inf;

queue < int > q;
q.push ( 1 );

int i;
while ( !q.empty() )
{
int s = q.front(); q.pop();
int size = v[s].size();

for ( i = 0; i < size; i++ )
{
int t = v[s][i];

if ( vis[t] == 0 && gf[s][t] != 0 )
{
vis[t] = min ( vis[s], gf[s][t] );
pre[t] = s;
q.push ( t );
}
}
}

int p = vis;

if ( p == 0 ) return p;

inc_flow( 2, p );
return p;
}

int main ()
{
//freopen ( "input.txt", "r", stdin );
//freopen ( "output.txt", "w", stdout );

int kase;
scanf ( "%d", &kase );
gets ( buf );
gets ( buf );

int flag = 0;
while ( kase-- )
{
if ( flag  ) nl;
flag = 1;

m2.clear();
club.clear();
pol.clear();
m.clear();
memset ( adj, 0, sizeof adj );

node = 3; //Node 1 and 2 are reserved for source and sink

while ( 1 )
{
if ( gets ( buf ) == NULL ) break;
if ( buf == 0 ) break;

//puts ( buf );

char *p = strtok ( buf, " " );
sscanf ( p, "%s", b1 );
if ( m.find( b1 ) == m.end() )
{
m[b1] = node;
m2[node] = b1;
node++;
}

int mem = m[b1]; //Member

p = strtok ( NULL, " " );
sscanf ( p, "%s", b1 );

if ( m.find ( b1 ) == m.end() )
{
m[b1] = node;
node++;
pol.pb ( node - 1 );
}

int party = m[b1]; //Party
adj[mem][party] = 1; // Member to party cap = 1

p = strtok ( NULL, " " );

while ( p != NULL )
{
sscanf ( p, "%s", b1 );

if ( m.find( b1 ) == m.end() )
{

m[b1] = node;
m2[node] = b1;
node++;
club.pb ( node - 1 );
}

int c = m[b1];
adj[c][mem] = 1; //Club to member cap = 1

p = strtok ( NULL, " " );
}

}

int csize = club.size(), i;
for ( i = 0; i < csize; i++ )
{
adj[club[i]] = 1; //Source to club cap = 1
}
int psize = pol.size();
for ( i = 0; i < psize; i++ )
{
int p = pol[i];
adj[p][node] = ( csize + 1 ) / 2  - 1 ; //Party to extranode cap = calculate
adj[node] = inf;//Extra node to sink cap = inf
node++;
}

node = node - 1; //Total node
build();

int flow = 0;
while ( 1 )
{
int f = path();
if ( f == 0 ) break;
flow += f;
}

if ( flow != csize )
{
printf ( "Impossible.\n" ); //Fixed after brianfry713 pointing it out.
}
else
{
//printf ( "%d\n", csize );
for ( i = 0; i < csize; i++ )
{
int c = club[i];
int lsize = v[c].size();
for ( int j = 0; j < lsize; j++ )
{
int tt = v[c][j];
if ( tt == 1 ) continue; //If club to source, skip

if ( gf[c][tt] == 0 ) //Club to a member. Residual zeor. Meaning there is flow
{
cout << m2[tt] << " " << m2[c] << endl;
}
}
}
}
}

return 0;
}
I am getting wa. Any special cases where this fails? Thank you for any kind of help Last edited by forthright48 on Thu Feb 07, 2013 8:54 am, edited 1 time in total.
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com