algorithm - bipartite matching in C++, what is wrong in my code? -


i have worked on bipartite matching problem, , got trouble solve it.

let me tell problem about.

as input form, gives me n, m number of people @ work , number of different kind of jobs in work. in following n lines, tells s tells how many kind of job ith person can do. in following s numbers, tell jobs can ith person can do. number of jobs si satisfy 1<=si<=m. then, if each person can work on 1 or less job @ time, how many jobs can done @ most?

this problem, , hope made sense you;) apologize poor english skill. returning point, code.

#include <stdio.h>  int n, m, dfscheck[1003], check[1003], input[1003][1003], back[1003], tmp, count=0;  void dfs(int num) {     int i, j;     if(check[num]==0)     {         tmp=-1;         check[num]=1;         return;     }     if(dfscheck[num]==1)         return;     dfscheck[num]=1;     for(j=1; j<=input[back[num]][0]; j++)     {         dfs(input[back[num]][j]);         if(tmp==-1)         {             back[input[back[num]][j]]=back[num];             return;         }     } }  int main(void) {     int i, j, flag ,k;     scanf("%d %d", &n, &m);     for(i=1; i<=n; i++)     {         scanf("%d", &input[i][0]);         for(j=1; j<=input[i][0]; j++)             scanf("%d", &input[i][j]);     }     for(i=1; i<=n; i++)     {         flag=0;         for(j=1; j<=input[i][0]; j++)             if(check[input[i][j]]==0)             {                 check[input[i][j]]=1;                 count++;                 flag=1;                 back[input[i][j]]=i;                 break;             }          if(flag==0)             for(j=1; j<=input[i][0]; j++)             {                 for(k=0; k<=1001; k++)                     dfscheck[k]=0;                 tmp=0;                 dfs(input[i][j]);                 if(tmp==-1)                 {                     back[input[i][j]]=i;                     count++;                 }             }     }     printf("%d", count);     return 0; }

the name of tmp bad understand code, so... tmp works flag in function dfs. tells whether has found matching.

i got wrong answer, neither runtime error nor time exceed. have read several different codes others have written, , couldn't find part wrong in code.

i have found code distinct others' in part don't define array, a[i], showing job matched ith person, opposite array in code. far understood codes, purpose of find out ith person has been matched before dfs. don't think case can happened. since no flow has come out of node of ith person, impossible flow go node of jobs node in max flow.

i wanted thoughts if useless, in case helps give me advices. anyway, let me have opinions!!! thank time.

one thing looks weird is:

            if(tmp==-1)             {                 back[input[i][j]]=i;                 count++;                 // expect see "break;" here             }

if find way assign person job increment count, , carry on trying see if can find alternative way assign same person. means may end assigning same person multiple jobs!

i recommend inserting "break;" statement once have found job person.


Comments

Post a Comment

Popular posts from this blog

PHP and MySQL WP -

i trying accomplish 2 things here code. writing php directly wp page using insert php plugin. 1) query mysql database , return results 1 column 4 columns. 2) make each result own hyperlink directs user new wp page runs new query on page. i able query show results , turn results dynamic hyperlink, cannot formatting down. right returns result 1 column. here have: [insert_php] $servername = "localhost"; $username = "login"; //edited privacy $password = "password"; //edited privacy $database = "database"; //edited privacy // create connection $conn = new mysqli($servername, $username, $password, $database); // check connection if ($conn->connect_error) { die("connection failed: " . $conn->connect_error); } echo "connected successfully"; //get results database $result = mysqli_query($conn,"select mine mines order mine"); $all_property = array(); //declare array saving property //showing proper...
Read more

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

go - golang pprof for c library code -

i have been trying profile golang application pprof, seems details of c code(linked static library) missed in output result. flame graph from frame graph can see c code time consuming reported within "runtime._externalcode", no details @ all. , sure static library compiled debug enable. so there way make pprof details(like stack trace) of 3rd party c code? or there other golang profiling tool this?
Read more