#include <stdio.h>
#include <stdlib.h>
int adjmat[10][10];
struct banks
{
    int netAmount;
    char name;
    char types[3];
};
struct Pair {
    int first;
    char second;
};
int GetMinIndex(struct banks listOfAmounts[],int numBanks)
{
    int min=INT_MAX,minIndex=-1;
    for(int i=0;i<numBanks;i++)
    {
        if(listOfAmounts[i].netAmount==0)
            continue;
        if(listOfAmounts[i].netAmount < min)
        {
            minIndex=i;
            min=listOfAmounts[i].netAmount;
        }
    }
    return minIndex;
}
int getSimpleMaxIndex(struct banks listOfNetAmounts[],int numBanks){
    int max=INT_MIN, maxIndex=-1;
    for(int i=0;i<numBanks;i++){
        if(listOfNetAmounts[i].netAmount == 0) continue;

        if(listOfNetAmounts[i].netAmount > max){
            maxIndex = i;
            max = listOfNetAmounts[i].netAmount;
        }
    }
    return maxIndex;
}/*
struct Pair getMaxIndex(struct banks listOfNetAmounts[], int numBanks, int minIndex, struct banks input[], int maxNumTypes)
{
    int max = INT_MIN;
    int maxIndex = -1;
    char matchingType[100];

    for (int i = 0; i < numBanks; i++) {
        if (listOfNetAmounts[i].netAmount == 0) continue;
        if (listOfNetAmounts[i].netAmount < 0) continue;

        //TODO
        //see complexity of intersection

        char v[maxNumTypes][100];
        char *ls = set_intersection((char *)listOfNetAmounts[minIndex].types, (char *)listOfNetAmounts[minIndex].types + listOfNetAmounts[minIndex].numTypes * 100, (char *)listOfNetAmounts[i].types, (char *)listOfNetAmounts[i].types + listOfNetAmounts[i].numTypes * 100, (char *)v);

        if ((ls - (char *)v) / 100 != 0 && max < listOfNetAmounts[i].netAmount) {
            max = listOfNetAmounts[i].netAmount;
            maxIndex = i;
            strcpy(matchingType, v[0]);
        }
    }

    //if there is NO such max which has a common type with any remaining banks then maxIndex has -1
    // also return the common payment type
    struct pair result;
    result.first = maxIndex;
    strcpy(result.second, matchingType);
    return result;
}*/
struct BankAndType {
    int bankIndex;
    char paymentType;
};

struct BankAndType getMaxIndex(struct banks* listOfNetAmounts, int numBanks, int minIndex, struct banks* input, int maxNumTypes) {
    int max = INT_MIN;
    int maxIndex = -1;
    char matchingType = '\0';

    for (int i = 0; i < numBanks; i++) {
        if (listOfNetAmounts[i].netAmount == 0 || listOfNetAmounts[i].netAmount < 0) {
            continue;
        }

        for (int j = 0; j < listOfNetAmounts[i].types; j++) {
            char currentType = listOfNetAmounts[i].types[j];

            for (int k = 0; k < minIndex; k++) {
                if (listOfNetAmounts[k].netAmount == 0 || listOfNetAmounts[k].netAmount > 0) {
                    continue;
                }

                for (int l = 0; l < listOfNetAmounts[k].types; l++) {
                    if (currentType == listOfNetAmounts[k].types[l]) {
                        if (listOfNetAmounts[i].netAmount > max) {
                            max = listOfNetAmounts[i].netAmount;
                            maxIndex = i;
                            matchingType = currentType;
                        }
                    }
                }
            }
        }
    }

    struct BankAndType result = { maxIndex, matchingType };
    return result;
}
void Minimizecashflow(int numBanks,struct banks input[6],char aindexOf[6],int numTras,int adjmat[6][6],int maxTypes)
{


   struct banks listOfNetAmounts[numBanks];
   for(int b=0;b<numBanks;b++)
   {
       listOfNetAmounts[b].name=input[b].name;
       for(int i=0;i<numBanks;i++)
       {
            listOfNetAmounts[b].types[i]=input[b].types[i];
       }

       int amount=0;
       for(int i=0;i<numBanks;i++){
            amount += (adjmat[i][b]);
        }
       for(int j=0;j<numBanks;j++){
            amount += ((-1) * adjmat[b][j]);
        }


        listOfNetAmounts[b].netAmount = amount;

   }




   struct Pair  ansGraph[numBanks][numBanks];
   int numZeroNetAmounts=0;
   int maxIndex=0;

    for(int i=0;i<numBanks;i++){
        if(listOfNetAmounts[i].netAmount == 0)
            numZeroNetAmounts++;
    }


    while(numZeroNetAmounts!=numBanks){

        int minIndex=GetMinIndex(listOfNetAmounts, numBanks);
        struct Pair maxAns = getMaxIndex(listOfNetAmounts, numBanks, minIndex,input,maxTypes);
        int maxIndex = maxAns.first;

       if(maxIndex == -1){

            (ansGraph[minIndex][0].first) += abs(listOfNetAmounts[minIndex].netAmount);
            //(ansGraph[minIndex][0].second) = *(input[minIndex].types.begin());

            int simpleMaxIndex = getSimpleMaxIndex(listOfNetAmounts, numBanks);
            (ansGraph[0][simpleMaxIndex].first) += abs(listOfNetAmounts[minIndex].netAmount);
           // (ansGraph[0][simpleMaxIndex].second) = *(input[simpleMaxIndex].types.begin());

            listOfNetAmounts[simpleMaxIndex].netAmount += listOfNetAmounts[minIndex].netAmount;
            listOfNetAmounts[minIndex].netAmount = 0;

            if(listOfNetAmounts[minIndex].netAmount == 0) numZeroNetAmounts++;

            if(listOfNetAmounts[simpleMaxIndex].netAmount == 0) numZeroNetAmounts++;

        }
        else{
            int transactionAmount;
            if(listOfNetAmounts[minIndex].netAmount < listOfNetAmounts[maxIndex].netAmount)
            {
                 transactionAmount=listOfNetAmounts[minIndex].netAmount;
            }
            else
            {
                 transactionAmount=listOfNetAmounts[maxIndex].netAmount;
            }

            (ansGraph[minIndex][maxIndex].first) += (transactionAmount);
           // (ansGraph[minIndex][maxIndex].second) = maxAns.second;

            listOfNetAmounts[minIndex].netAmount += transactionAmount;
            listOfNetAmounts[maxIndex].netAmount -= transactionAmount;

            if(listOfNetAmounts[minIndex].netAmount == 0) numZeroNetAmounts++;

            if(listOfNetAmounts[maxIndex].netAmount == 0) numZeroNetAmounts++;
        }

    }

   // printAns(ansGraph,numBanks,input);


}
int main()
{


     printf("\n---------------------------------------------------------------------------------------Welcome to CASH FLOW MINIMIZER SYSTEM--------------------------------------------------------------------------------------\n\n\n");
     int numBanks;
     printf("\nEnter The Number Of Banks:");
     scanf("%d",&numBanks);
     printf("\n----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\n\n");




     struct  banks input[numBanks];
     char aindexOf[numBanks];
     int maxTypes;

     printf("Enter The Details Of The Banks and Transactions As Stated:\n");
     printf("Bank Name , Number Of Payment Modes It has and the Payment Modes.\n");
     printf("\n----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\n\n");




     for(int i=0;i<numBanks;i++)
     {
         if(i==0)
             printf("WorldBank:");
         else{
             printf("Bank: %d ",i);
         }


         fflush(stdin);
         printf("\nEnter name of bank:");
         fflush(stdin);
         scanf("%c",&input[i].name);
         aindexOf[i]=input[i].name;
         fflush(stdin);
         printf("\nEnter Number Of Modes: ");
         int numTypes;
         scanf("%d",&numTypes);
         printf("\nClick \nPhone pay-1, \nPaytm-2, \nGoogle pay-3::");


         if(i==0)
            maxTypes=numTypes;

           int inputTypesofpayment;
           input[i].types[0]=0;//gpay
           input[i].types[1]=0;//paytm
           input[i].types[2]=0;//phonepe
           while(numTypes--)
           {

               scanf("%d",&inputTypesofpayment);
               input[i].types[inputTypesofpayment]=1;
           }
                 printf("\n----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\n\n");

     }



     printf("\nEnter number of Trasaction.");
     int NumTras;
     scanf("%d",&NumTras);
     int adjmat[numBanks][numBanks];
     for(int i=0;i<numBanks;i++)
     {
         for(int j=0;j<numBanks;j++){
            adjmat[i][j]=0;
         }

     }




     printf("Debtor Bank , creditor Bank and amount\n");
     for(int i=0;i<NumTras;i++)
     {
         printf("\n%d: th trasaction:",i+1);
         fflush(stdin);
         char fBank,sBank;
         int amount;
         fflush(stdin);
         scanf("%c %c",&fBank,&sBank);
         fflush(stdin);
         scanf("%d",&amount);
         fflush(stdin);
         int retindf=0;
         int retinds=0;
         for(int i=0;i<numBanks;i++)
         {
             //printf("\nI am in");
             if(aindexOf[i]==fBank)
                 retindf=i;
             if(aindexOf[i]==sBank)
                  retinds=i;
         }

        adjmat[retindf][retinds]=amount;

     }


     /*for(int i=0;i<numBanks;i++)
     {
         for(int j=0;j<numBanks;j++){
            printf("%d ",adjmat[i][j]);
         }
         printf("\n");

     }*/


    Minimizecashflow(numBanks,input,aindexOf,NumTras,adjmat,3);

    return 0;

}