10511 - Councilling

[windows2k]

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

[Per]

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]

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]

I have thought the method to solve it.
Thx

[lucindo]

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??

[Noim]

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.
can any one give me some hints about this?

thanks

[Whinii F.]

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.

[Noim]

Thanks for Help.
I got Accepted at last.

[hujialie]

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]

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]

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]

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]

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]

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;
}

[forthright48]

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