![:(](./images/smilies/icon_frown.gif)
Could someone give me a hint?
thx
Moderator: Board moderators
Code: Select all
1
john yatch
Code: Select all
1
john yatch
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;
}
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;
}