## 10511 - Councilling

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

Moderator: Board moderators

### 10511 - Councilling

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

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

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
windows2k
Experienced poster

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

### 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
lucindo
New poster

Posts: 11
Joined: Thu Sep 05, 2002 2:35 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....
Noim
Learning poster

Posts: 88
Joined: Sun Oct 13, 2002 6:11 am

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
Whinii F.
Experienced poster

Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea

Thanks for Help.
I got Accepted at last.
__nOi.m....
Noim
Learning poster

Posts: 88
Joined: Sun Oct 13, 2002 6:11 am

### 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?
hujialie
New poster

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

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
`1john yatch`

I think than should output "Impossible" isnt it?

thanks!
coconut
New poster

Posts: 7
Joined: Thu May 27, 2004 7:23 pm
Location: Honolulu

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.
ZhangChi
New poster

Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm

### 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.
chenta
New poster

Posts: 1
Joined: Thu Jul 11, 2002 11:19 am

### 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[40100];string in[40100];int type[40100];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[40100],qf,qe,parent[40100],mark[40100];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[100],str[100];   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[0] ){         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;)
Angeh
Experienced poster

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

### 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***********/#pragma comment (linker,"/STACK:16777216")#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[2000];char b1[200], b2[100];map < int, string > m2;vector < int > club, pol;int node;map < string, int > m;int adj[3000][3000];int gf[3000][3000];vector < int > v[3000];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 )            {                gf[i][j] = adj[i][j];                v[i].pb ( j );                v[j].pb ( i );            }        }    }}int vis[3000];int pre[3000];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[1] = 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[2];    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] == 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[1][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][2] = 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
forthright48
New poster

Posts: 13
Joined: Wed Mar 14, 2012 11:57 am